素因子分解算法python语言_[原创]magma,/PARI/GP中文文档ECC初步:
1
2011-2-10 16:13
Example: Diffie-Hellman key exchange
q := RandomPrime (160: Proof := false);
q;
Ilog2 (q); 2进制位数
repeat
got_it, p := RandomPrime (1024, 1, q, 1000 : Proof := false);
until got_it;
> p;
Ilog2 (p); 2进制位数
tmp := Random(p);
exp := (p - 1) div q;
> g := Modexp (tmp, exp, p);
> g;
Modexp (g, q, p);
A_priv := Random (p-1);
> A_pub := Modexp (g, A_priv, p);
> B_priv := Random (p-1);
> B_pub := Modexp (g, B_priv, p);
> A_sec := Modexp (B_pub, A_priv, p);
> B_sec := Modexp (A_pub, B_priv, p);
A_sec eq B_sec;
A_sec;
1442887065756557081811008885496150418808858816401
159
1651626359469589873102835252970210623774108012103316760123483790491795927792372\
0911163345405386569084216526903485568850519787298376968456439442825925293266689\
5321313697674085713119066460654757154900942213051543220536646001952121896818924\
040862028079007349903890347825426890204440412990981184175301600052642601
1023
8396531707945536590388438602520909841199441225289405372543328552794730731140493\
2359964273401131497951715591859147928675735938983332715282809702511549282280553\
7257551736967439068907583093988590627324758408980681857356806656895703862655226\
21592741188383919546746662841766547810852182714292042706175121823048920
1
true
5144176322605153756984581571117138785000992400326941258925591946874878623433746\
0604279696565409179426210808910383200849384907133032735704943374046999690951643\
2436947000024050385014162242822642019010522453269701147220601715739683999992133\
82708798156652799536437768737718826497886878455615884529095508002441544
Hastad’s broadcast attack on RSA
一种广播攻击RSA，原理是孙子定理，M是明文
1024位的3个不同素因子密匙加密，密文只要三次出现在广播中，就能被还原为明文
函数都有，方便啊
孙子谁知道叫啥名？
N1 := RSAModulus (1024, 3);
N1;
N2 := RSAModulus (1024, 3);
> N2;
N3 := RSAModulus (1024, 3);
> N3;
N1 lt N2;
N2 lt N3;
M := Random (N3);
M;
C1 := Modexp (M, 3, N1);
C2 := Modexp (M, 3, N2);
> C3 := Modexp (M, 3, N3);
> C1;
C2;
C3;
ciphertexts := [C1, C2, C3];
moduli := [N1, N2, N3];
> Cprime := CRT (ciphertexts, moduli);
> Cprime;
Iroot (Cprime, 3);
1191394973498639734758356886734022915243239449328167951285523220116137226774353\
9176019504000834314079698783061932470536725623631410436123478027064344268960243\
7364284793780727456801948423015783019014512753812345243506372098537224435020854\
359848856524899561390988681729562607944000515285564642890387968646827499
1284091640527210186131874393840544095987650982828046236855841544838591571499173\
1866298541100429948705032672190648692663519160856065108275130184865262172800857\
3386565091923148415442237752544661929267855180513383588291450048199800697918748\
507167493425580851595456232294309693917376008568189561641242801970999677
1079659736287944257378805435089043111076737452648956984975669952706815978980298\
6622188200179949052343959127642578022293418583950295309545564738766859693242769\
4693380883751647379784344459796750774988626755269852596427483690743738731140884\
348140421109007063610908180910131454760258796787470341628217212597348237
true
false
1065483725312210764607948804191105051984095256035964212419006647799252157478385\
6334603416677964537633362076010548745454399657943033796697306916247944219685014\
0939319424884142058105500815238082740397639628813948210482176247050158934106124\
746653542454869790679475333470275013517239162467216886783299705473412909
1924084294474065804173347971493633606471329611790262546576596759680624764052803\
5603855496570716546643207106535414986292485635347396779535480273771479179167217\
3693328315426059122287765033711613884956437027782317188733396126117328636526178\
56045629675048923525525556790596952847575213284810439009623226349241181
2376889508979652383834732793528970881037787915415560763427681345964168211539753\
9459811216757749141242641330948276279731548487493134449049621818003288666629642\
7107106879554253057484348013589960001869058474748052966098867953029654679461620\
23532932526818702053588818851843636547054094394130454387535970722272602
9829945919241924969246733746114350726954659414719450874216585166522394276356794\
2155581726235090790726244419011366315696252177358211842671261671704146797693032\
4127009226220296583554431629646178702563947023823646933477546640724280367260704\
60397221620150214727998193463203577893197619215531865820102008407048363
1209596332738531401730087906166277185149003439550896493434779023414176254956043\
2315223272998309692796071291550238017300406144851952116784618699424318350163383\
0623537152218766553695974915925794283159542108168794504904334776472147979805682\
6758534588794554448343265778153818561455153300516738560092882314196842832629908\
0893739204365221773895249374020378141139662196321124225421875676893136477652571\
3686545436735346949304011400137889800182213384268514452639716065687280905474249\
3802438205591679005814273361702058789755016475321682260206347613282853189661176\
9660825254532364209370935104037356711766047967220791151295375750619273595873632\
4374572156522931220632061230921514554158001662097184542577633122532256834871889\
8076147371585186855569055341508199943243209040147941375606027322104397902862026\
8383567305221626770449237160147609033402505962655670767253025758997906062878114\
56219237300141333155757438706370370416335624953661405429
1065483725312210764607948804191105051984095256035964212419006647799252157478385\
6334603416677964537633362076010548745454399657943033796697306916247944219685014\
0939319424884142058105500815238082740397639628813948210482176247050158934106124\
746653542454869790679475333470275013517239162467216886783299705473412909
-----------------------------
http://magma.maths.usyd.edu.au/magma/pdf/examples.pdf
Chapter 28
Elliptic Curve Cryptography
28.5. EXAMPLE: ECDSA------------例子很易懂，但选安全曲线就难了
随机选一次系数a,常数b，X96-2荐a=-3,因为在常规表示和雅可比式变换中，有个表达式a=-3最方便，硬件计算快
p := RandomPrime (100);
> K := GF(p);
E := EllipticCurve ([Random(K), Random(K)]);
E;
p := RandomPrime (100);
> K := GF(p);
E := EllipticCurve ([-3, Random(K)]);
E;
为了选安全曲线， repeat重复选：
p := RandomPrime (100);
> K := GF(p);
> repeat
repeat> E := EllipticCurve ([-3, Random(K)]);
repeat> fo := FactoredOrder (E);---------------要大素数阶
repeat> n := fo[#fo][1];
repeat> until Ilog2 (n) ge 88; ------------------2进制位比域小
> Ilog2 (n);
IsSupersingular(E);-------------------------------要非超奇异，
P=100位,a随机选签名过程
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
69611886555621063506166355926 over GF(157135449112378660707313000637)
[ <2, 2>, <3, 1>, <7, 2>, <17, 1>, <181, 1>, <2099, 1>, <596447989, 1>,
<69372018557, 1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
65388471706181964183230162768 over GF(157135449112378660707313000637)
[ <73, 1>, <55079, 1>, <8304629, 1>, <4705925295986567, 1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
126592445929249859850032581477 over GF(157135449112378660707313000637)
[ <5431, 1>, <7687, 1>, <3763894893517636036879, 1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
111827571730976256692740142243 over GF(157135449112378660707313000637)
[ <2, 3>, <3, 1>, <17, 1>, <36583, 1>, <10527728854582845299309, 1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
147021577696058357454344453248 over GF(157135449112378660707313000637)
[ <2, 1>, <3, 3>, <406169, 1>, <3777283, 1>, <1896680213262977, 1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
59756192161956097905575248378 over GF(157135449112378660707313000637)
[ <2, 1>, <3, 1>, <151, 1>, <263, 1>, <617, 1>, <9941, 1>, <107516467533934661,
1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
55629840512052832330840836298 over GF(157135449112378660707313000637)
[ <2, 2>, <7, 1>, <151, 1>, <37165432618821789909906481, 1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
151057113700827850188583571502 over GF(157135449112378660707313000637)
[ <2, 2>, <11, 1>, <17, 1>, <29, 1>, <640740839, 1>, <11305562359133503, 1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
76416094973710013389958980325 over GF(157135449112378660707313000637)
[ <2, 1>, <3, 2>, <7, 1>, <11093, 1>, <112422855763737340508257, 1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
139000244472820858413576632031 over GF(157135449112378660707313000637)
[ <2, 2>, <3, 1>, <5, 1>, <37, 1>, <607, 1>, <12746273, 1>, <9148487302593389,
1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
66914405844156577851178843582 over GF(157135449112378660707313000637)
[ <3, 1>, <7, 1>, <23, 1>, <8423, 1>, <38624266031016342385927, 1> ]
Elliptic Curve defined by y^2 = x^3 + 157135449112378660707313000634*x +
143325094039473088283650924294 over GF(157135449112378660707313000637)
[ <2, 1>, <3, 1>, <5, 2>, <1047569660749190309106427747, 1> ]
89
false
安全曲线重多，100位下就有上面这些，选好了安全曲线，下面就找了个基点，并求基点的阶，基点更多，安全曲线数*基点数*离散指数------大O，小O，ECC的安全指数可能真是指数级。。。
用的是下面曲线：
y^2 = x^3 + 157135449112378660707313000634*x +
143325094039473088283650924294 over GF(157135449112378660707313000637)
[ <2, 1>, <3, 1>, <5, 2>, <1047569660749190309106427747, 1> ]
n;----------------------------------------------------E中n阶子循环群这
P := Random(E) * (Order(E) div n); -----找了个基点
P;
Order(P) eq n; -------------------------------------基点的阶
d := Random(n);
Q := d*P; 随机选的d
Q;
M := Random(n); 甲方 要发的明文
> M;
k := Random(n); 甲方随机选k
kp_seq := ElementToSequence (k*P); 计算点乘k*P，表示成点
kp_seq;
r := (IntegerRing()!kp_seq[1]) mod n; 不管k*P多大 都要mod n
s := (Modinv (k, n) * (M + d*r)) mod n; 经过求模逆，模乘，模加，签好了
> s;
r in [1..n-1];
s in [1..n-1];
w := Modinv (s, n); 下面是乙方验证，也要经过求点乘，模逆，模乘，模加
u1 := M*w mod n;
u2 := r*w mod n;
temp := u1*P + u2*Q;
temp;
temp_seq := ElementToSequence (temp);
> v := (IntegerRing()!temp_seq[1]) mod n;
> v;
v eq r; 验证EQUAL,OK
Elliptic Curve defined by y^2 = x^3 + 546406580005247203836151279129*x +
230151935666323598335959051729 over GF(966371258750148727567627105897)
[ <3, 2>, <149, 1>, <720634793997127170564126541, 1> ]三个循环子群，，经过上面REPEAT选，已知攻击都被棑除，阶720634793997127170564126541的中的点安全,循环子群点阶如过恰=曲线阶，会被多项式级的同构攻击。不过恰=可能性太小了
89
false
720634793997127170564126541
(156817043070046010480672869099 : 138406249392994102180675488148 : 1)基点座标
true
(823452749814859867769709264217 : 409839153103190558971036321686 : 1)
314368839904612579301554984 计算点乘d*P;
[ 750750203409670127154353456215, 274010688382591384982046792082, 1 ]
337341060791448293483425930 明文，已被表示成曲线的点，明文，域元素，曲线点可互相转化。X9-62里有，有三种形式，不太难懂，这ElementToSequence函数一定包括了这功能
true
true
(750750203409670127154353456215 : 274010688382591384982046792082 : 1)
569382858660742597097727034 计算点乘 k*P
true
下面P=100位,a=-3签名过程：
Elliptic Curve defined by y^2 = x^3 + 344566048772404937900222995696*x +
122613265914087061833345770776 over GF(344566048772404937900222995699)
[ <2, 4>, <173, 1>, <70009, 1>, <1778085018158714891237, 1> ]
Elliptic Curve defined by y^2 = x^3 + 344566048772404937900222995696*x +
44333872090216421338353867400 over GF(344566048772404937900222995699)
[ <108421, 1>, <189401, 1>, <16779414654143966807, 1> ]
Elliptic Curve defined by y^2 = x^3 + 344566048772404937900222995696*x +
168372939479581669368060393010 over GF(344566048772404937900222995699)
[ <2, 2>, <5, 1>, <41, 1>, <420202498502932494553451531, 1> ]
88
false
420202498502932494553451531
(19629684444028095682059018614 : 313332333218081159316329285802 : 1)
true
(185904318135579502698063049655 : 337526345404850851784130027470 : 1)
210595421815090177972701173
[ 71071577049370184377915299896, 30419639182367625537958244039, 1 ]
178411782669416518303895082
true
true
(71071577049370184377915299896 : 30419639182367625537958244039 : 1)
57354802374592798381991157
true
估记最少得把序，扩域多项式环搞透才能下面
http://magma.maths.usyd.edu.au/magma/pdf/examples.pdf
格攻击
Chapter 29
LLL and Lattice Based Ciphers
格密码
Chapter 33
Miscellaneous
NTRU