Ch−¬ng tr×nh KC-01:
Nghiªn cøu khoa häc
ph¸t triÓn c«ng nghÖ th«ng tin
vµ truyÒn th«ng
§Ò tµi KC-01-01:
Nghiªn cøu mét sè vÊn ®Ò b¶o mËt vµ
an toµn th«ng tin cho c¸c m¹ng dïng
giao thøc liªn m¹ng m¸y tÝnh IP
B¸o c¸o kÕt qu¶ nghiªn cøu
§¶m b¶o to¸n häc cho c¸c hÖ mËt
QuyÓn 3B: “Sinh tham sè an toµn cho hÖ mËt Elgamal”
Hµ NéI-2002
B¸o c¸o kÕt qu¶ nghiªn cøu
§¶m b¶o to¸n häc cho c¸c hÖ mËt
QuyÓn 3B: “Sinh tham sè an toµn cho hÖ mËt Elgamal”
Chñ tr× nhãm nghiªn cøu:
TS. LÒu §øc T©n
Môc lôc
ch−¬ng i- vai trß cña sè nguyªn tè d¹ng p=2q+1
TRONG MËT M·
më ®Çu
1.1 BµI TO¸N logarit rêi r¹c vµ c¸c øng dông trong
mËt m·
1.1.1 Bµi to¸n logarit rêi r¹c trªn tr−êng GF(p)
1.1.2 HÖ mËt Elgamal
1.1.3 Ch÷ ký sè Elgamal
1.1.4 S¬ ®å ph©n phèi kho¸ Diffie-Hellman
1.2 c¸c thuËt to¸n t×m logarit rêi r¹c
1.2.1 ThuËt to¸n Shanks
1.2.2 ThuËt to¸n Pohlig - Hellman
1.2.3 ThuËt to¸n sµng bËc q
1.2.4 ThuËt to¸n sµng tr−êng sè
Tµi liÖu dÉn
ch−¬ng ii-sinh sè nguyªn tè lín b»ng ph−¬ng
ph¸p t¨ng dÇn ®é dµi
më ®Çu
2.1 Mét sè kÕt qu¶ trong lý thuyÕt sè
2.2 ThuËt to¸n Pocklington
2.2.1 ThuËt to¸n kiÓm tra tÝnh nguyªn tè Pocklington trªn líp LF
2.2.2 §¸nh gi¸ x¸c suÊt sai lÇm cña thuËt to¸n Pock-testF
2.2.3 ThuËt to¸n sinh sè nguyªn tè trªn líp LF
2.2.3.1 Më ®Çu
2.2.3.2 Mét sè ph©n tÝch vÒ kh¶ n¨ng tån t¹i sè nguyªn tè ®é dµi n
trong líp sè LF
2.3 ThuËt to¸n sinh c¸c sè nguyªn tè ≥n bit tõ
thuËt to¸n sinh c¸c sè nguyªn tè <n bit
2.3.1 Më ®Çu
2.3.2 ThuËt to¸n
2.3.3 Ph©n tÝch kh¶ n¨ng sinh c¸c sè nguyªn tè dé dµi n cña thuËt to¸n
2.3.4 Ph©n tÝch thêi gian thùc hiÖn viÖc sinh mét sè nguyªn tè ®é dµi n
2.3.5 Sù tån t¹i thuËt to¸n nhanh sinh ®−îc toµn bé c¸c sè nguyªn tè
2.3.5.1 ThuËt to¸n
2.3.5.2 KÕt luËn
Tµi liÖu dÉn
ch−¬ng iii-ch−¬ng tr×nh sinh sè nguyªn tè
m¹nh cho hÖ mËt elgamal
më ®Çu
3.1 líp Lp vµ sè l−îng sè nguyªn tè trong líp lp
3.1.1 Líp Lp(k)
3.1.2 Sè c¸c sè nguyªn tè ®é dµi n=3klogp bit cã trong líp Lp(k)
3.1.3 ThuËt to¸n sinh sè nguyªn tè n bit trªn c¸c líp Lp(k) víi p nhá
3.1.4 Tr−êng hîp p=2
3.2 ViÖc sinh c¸c sè nguyªn tè m¹nh vµ gÇn m¹nh
3.2.1 Kh¸i niÖm sè nguyªn tè m¹nh vµ gÇn m¹nh
3.2.2 Sè nguyªn tè Sophie
3.2.3 ThuËt to¸n sinh sè nguyªn tè gÇn m¹nh
3.2.3.1 ThuËt to¸n
3.2.4 ThuËt to¸n sinh nhanh c¸c nh©n nguyªn tè lín ®−îc gµi ®Æt
3.2.4.1 Ph−¬ng ph¸p sinh nhanh tõ sè nguyªn tè nhá
3.2.4.2 Ph−¬ng ph¸p gÊp ®«i ®é dµi tõ sè nguyªn tè lín
3.3 tÝnh to¸n trªn c¸c sè lín
3.3.1 PhÐp nh©n sè lín
3.3.2 PhÐp chia hai sè lín
3.3.3 PhÐp luü thõa modulo c¸c sè lín
3.3.3.1 C«ng thøc luü thõa theo khai triÓn nhÞ ph©n cña sè mò
3.3.3.2 C«ng thøc luü thõa theo khai triÓn a ph©n cña sè mò
3.3.3.3 Ph−¬ng ph¸p khai triÓn sè mò theo c¬ sè thay ®æi (c¬ sè ®éng)
tµi liÖu dÉn
phô lôc 1. c¸c kÕt qu¶ thö nghiÖm
1.1 Giíi thiÖu vÒ phÇn mÒm
1.1.1 VÒ l−u tr÷ c¸c sè nguyªn tè m¹nh sinh ®−îc
1.1.2 VÊn ®Ò ghi l¹i b»ng chøng vÒ tÝnh nguyªn tè vµ tÝnh nguyªn tè
m¹nh cña c¸c sè sinh ®−îc
1.2 Kh¶ n¨ng sinh sè nguyªn tè m¹nh cña ch−¬ng tr×nh
1.2.1 Sè nguyªn tè m¹nh lín nhÊt sinh ®−îc
1.2.2 Mét sè kÕt luËn thèng kª thu ®−îc
phô lôc 2. VÝ dô vÒ sè c¸c sè Pepin, Pocklington
vµ Sophie
1. B¶ng sè l−îng c¸c sè Pepin =r216+1 víi r lÎ vµ kh«ng qu¸ 32 bit
2. B¶ng sè l−îng c¸c sè Pocklington q=R(216+1)+1 vµ sè Sophie kh«ng
qu¸ 32 bit
3. B¶ng tÊt c¶ c¸c sè Sophie d¹ng q=R(216+1)+1 vµ kh«ng qu¸ 32 bit
3.1 B¶ng tÊt c¶ c¸c sè Sophie d¹ng q=R(216+1)+1 (tõ 25 ®Õn 31 bit)
3.2 B¶ng tÊt c¶ c¸c sè Sophie d¹ng q=R(216+1)+1 (32 bit)
