Hình 4.14. Phân tích modulus c a rabin v i m t ch ng trìnhủ ớ ộ ươ
con gi i mã cho tr c.ả ướ
B i v y giá tr x s thu đ c b c 3. Ti p theo xét b c 4.ở ậ ị ẽ ượ ở ướ ế ướ
Nh n th y r ng xậ ấ ằ 12 = r2 (mod n). Đi u đó d n t i xề ẫ ớ 1 ≡ ±r (mod n)
ho c xặ1 ≡ ±wr (mod n), trong đó w là m t trong các căn b c haiộ ậ
không t m th ng c a 1 modulo n. Trong tr ng h p th hai taầ ườ ủ ườ ợ ứ
có :
n(x1-r )(x1+r)
song n không ph i là c c a m t th a s nào v ph i. B i v y,ả ướ ủ ộ ừ ố ở ế ả ở ậ
vi c tính UCLN(xệ1 +r,n)(ho c UCLN(xặ1-r, n)) ph i d n t i ho c pả ẫ ớ ặ
ho c q, và nh v y phép phân tích n đ c hoàn thành.ặ ư ậ ượ
Ta s tính xác su t thành công c a thu t toán này trên t t cẽ ấ ủ ậ ấ ả
(n-1) phép ch n ng u nhiên r. V i hai th ng d khác không rọ ẫ ớ ặ ư 1 và
r2 , đ nh nghĩa: ị
r1 ~ r2 ⇔ r12 ≡ r22 (mod n)
D dàng th y r ng r ~ r v i m i r, rễ ấ ằ ớ ọ 1 ~ r2 cũng có nghĩa là r2 ~
r1; r1 ~ r2 và r2 ~ r3 thì r1 ~ r3 . Đi u đó cho ta th y r ng quan h ~ làề ấ ằ ệ
m t quan h t ng đ ng. Các l p t ng đ ng c a Zộ ệ ươ ươ ớ ươ ươ ủ n\{0} đ uề
có b n ph n t , l p t ng đ ng ch a r là t p ố ầ ử ớ ươ ươ ứ ậ
[r] = {±r, ±wr (mod n)}
trong đó w là căn b c hai không t m th ng c a 1 modulo n.ậ ầ ườ ủ
1. Ch n m t s ng u nhiên r , 1ọ ộ ố ẫ ≤ r ≤ n-1
2. Tính y = r2 - B2/4 mod n
3. G i ch ng trình con A(y) đ tìm b nọ ươ ể ả
gi i mã xả
4. Tính x1 = x+B/2
5. If x1 ≡ ± r (mod n) then quit (không
thành công)
Else UCLN(x1+r,n)=p ho c q (thànhặ
công)
Trong thu t toán đ c trình bày hình 4.14, hai giá tr r b tậ ượ ở ị ấ
kỳ trong cùng m t l p t ng đ ng s d n t i cùng m t giá tr y.ộ ớ ươ ươ ẽ ẫ ớ ộ ị
Bây gi xét giá tr x thu đ c t ch ng trình con A khi đã bi t y.ờ ị ượ ừ ươ ế
Ta có:
[y]={±y, ±wy}
N u r=ế±y thì thu t toán không thành công;ậ
trong khi n u r=ế±wy thì thu t toán s thànhậ ẽ
công. Vì r c ch n ng u nhiên, nên m t giáđượ ọ ẫ ộ
tr b t k trong b n giá tr có th u cùngị ấ ỳ ố ị ể đề
kh n ng. Ta k t lu n r ng xác su t thành côngả ă ế ậ ằ ấ
c a thu t toán là 1/2. ủ ậ
i u thú v là h m t rabin là an toàn iĐ ề ị ệ ậ đố
v i ph ng pháp t n công b n rõ ch n l c,ớ ươ ấ ả ọ ọ
mh mg h này l i hoàn toàn không an toàn iư ệ ạ đố
v i ph ng pháp t n công b m mã ch n l c.ớ ươ ấ ả ọ ọ
Thu t toán hình 4.14, ph n dùng ch ngậ ở ầ để ứ
minh s an toàn i v i phép t n công b n rõự đố ớ ấ ả
ch n l c c ng có th c dùng phá h m tọ ọ ũ ể đượ để ệ ậ
Rabin khi th c hi n t n công b n mã ch n l c!.ự ệ ấ ả ọ ọ
Trong ph ng pháp t n công b n mã ch n l c,ươ ấ ả ọ ọ
ch ng trình con A c thay b ng thu t toánươ đượ ằ ậ
gi i mã c a Bob.ả ủ
4.8. Các thu t toán phân tích th a s .ậ ừ ố
Đã có m t kh i l ng kh ng l các tìa li u v các thu tộ ố ượ ổ ồ ệ ề ậ
toán phân tích th a s và vi c nghiên c u k l ng s đòi h iừ ố ệ ứ ỹ ưỡ ẽ ỏ
ph i có m t cu n sách dày h n quy n sách này. đây ch c g ngả ộ ố ơ ể ở ỉ ố ắ
đ a ra m t cái nhìn khái quát bao g m vi c th o lu n s l c vư ộ ồ ệ ả ậ ơ ượ ề
các thu t toán phân tichs th a s t t nh t hi n th i và cách sậ ừ ố ố ấ ệ ờ ử
d ng chúng trong th c t . Ba thu t toán hi u qu nh t trên các sụ ự ế ậ ệ ả ấ ố
th t l n là sàng b c hai, thu t toán đ ng cong elliptic và sàngậ ớ ậ ậ ườ
tr ng s . Các thu t toán n i ti ng khác (nh ng thu t toán toán cóườ ố ậ ổ ế ữ ậ
tr c) bao g m ph ng pháp ướ ồ ươ ρ và thu t toán p-1 c a Pollard,ậ ủ
thu t toán p+1 c a Williams, thu t toán liên phân s và dĩ nhiên cậ ủ ậ ố ả
nh ng phép chia th .ữ ử
Trong toàn b ph n này, xchúng ta c ìng s nguyên n c nộ ầ ỏ ố ầ
phân tích ra th a s là m t s l . Phép chia th bao g m vi c chiaừ ố ộ ố ẻ ử ồ ệ
n
cho t ng s nguyên l cho t i . N u n < 10ừ ố ẻ ớ ế 12 thì đây là m tộ
ph ng pháp phân tích th a s h p lý m t cáchươ ừ ố ợ ộ
hoàn h o, tuy nhiên v i n l n h n nói chung taả ớ ớ ơ
ph i dùng các k thu t tinh t h n.ả ỹ ậ ế ơ
4.8.1. Ph ng pháp p-1ươ
Thu t toán p-1 c a Pollar (đ a ra vào năm 1947) là m t thíậ ủ ư ộ
d v m t thu t toán đ n gi n đ n khi đ c áp d ng v i các sụ ề ộ ậ ơ ả ơ ượ ụ ớ ố
nguyên l n. Thu t toán này (trình bày trên hình 4.15) có hai đ uớ ậ ầ
vào: s nguyên l n c n đ c phân tích và m t c n B. Có th môố ẻ ầ ượ ộ ậ ể
t thu t toán nh sau:ả ậ ư
Hình 4.15. Thu t toán phân tích th a s p-1.ậ ừ ố
Gi s p là c mhuyên t c a n và q ả ử ướ ố ủ ≤ B , v i m i mũớ ỗ
nguyên t pố(p-1). Khi đó
(p-1)B!
cu i vòng l p for (b c 2)ở ố ặ ướ
[ ]
n
Đ u vào: n và Bầ
1. a=2
2. For j=2 to B do
a = aj mod n
3. d = UCLN(a-1,n)
4. if 1 < d < n then
d là m t th a s c a n ộ ừ ố ủ
else
không tìm đ c th a s c a n ượ ừ ố ủ
(không thành công)
a ≡ 2B! (mod n)
nên a ≡ 2B! (mod p)
vì pn. nên theo đ nh ý Fermat ta có :ị
135979 × 115979
Trong tr ng h p này, phép phân tích s thànhườ ợ ẽ
công do 135978 ch g m các th a s nguyên tỉ ồ ừ ố ố
nh :ỏ
Vì th ế
135978 = 2 × 3 ×131 × 173
n u l y B ế ấ ≥ 173 thì ch c ch n r ng 135978ắ ă ằ B!
nh mong mu n.ư ố
Trong thu t toán có (B-1) lu th a theo modulo, m i lu c nậ ỹ ừ ỗ ỹ ầ
nhi u nh t là 2logề ấ 2B phép nhân modulo dùng thu t toán bìnhậ
ph ng và nhân. Vi c tính c chung l n nh t có th th c hi nươ ệ ướ ớ ấ ể ự ệ
trong th i gian O((log n)ờ3) b ng thu t toán Euclide. B i v y, đằ ậ ở ậ ộ
ph c t p c a thu t toán là O(B logB (log n)ứ ạ ủ ậ 2 +(log n)3). N u B làế
O((log n)i) v i m t s nguyên i xác đ nh nào đó thì thu t toán th cớ ộ ố ị ậ ự
s là thu t toán th i gian đa th c, tuy nhiên v i phép ch n B nhự ậ ờ ứ ớ ọ ư
v y, xác su t thành công s r t nh . M t khác, n u tăng kíchậ ấ ẽ ấ ỏ ặ ế
th c c a B lên th t l n (ch ng h n t i ?????????????? ) thìướ ủ ậ ớ ẳ ạ ớ
thu t toán s thành công nh ng nó s không th c hi n nhanh h nậ ẽ ư ẽ ự ệ ơ
phép chia th .ử
Nh v y, đi m b t l i c a thu t toán này là nó yêu c u nư ậ ể ấ ợ ủ ậ ầ
ph i có c nguyên t p sao cho (p-1) ch các th a s nguyên tả ướ ố ỉ ừ ố ố
bé. Ta có th d dàng xây d ng đ c h m t RSA v i modulus n=ể ễ ự ượ ệ ậ ớ
pq h n ch đ c vi c phân tích theo ph ng pháp này. Tr c tiênạ ế ượ ệ ươ ướ
tìm m t s nguyên t l n pộ ố ố ớ 1 sao cho p= 2p1+1 cũng là m t sộ ố
nguyên t và m t s nguyên t l n qố ộ ố ố ớ 1 sao cho q= 2q1+1 cũng là m tộ
s nguyên t (nh dùng m t trong các thu t toán ki m tra tínhố ố ờ ộ ậ ể
nguyên t Monte-Carlo nêu trong ph n 4.5). Khi đó modulo c aố ầ ủ
RSA n= pq s ch ng đ c cách phân tích theo ph ng pháp p-1.ẽ ố ượ ươ
Thu t toán đ ng cong elliptic m nh h n (đ c Lenstra xâyậ ườ ạ ơ ượ
d ng vào nh ng năm 1980) trên th c t là s t ng quát hoá c aự ữ ự ế ự ổ ủ
ph ng pháp p-1. Ta s không th o lu n v lý thuy t đây mà chươ ẽ ả ậ ề ế ở ỉ
nh n m nh r ng, thành công c a ph ng pháp đ ng cong ellipticấ ạ ằ ủ ươ ườ
tuỳ thu c vào tình hu ng t ng t : m t s nguyên “g n v i” p chộ ố ươ ự ộ ố ầ ớ ỉ
có các th a s nguyên t bé. Trong khi ph ng pháp p-1 ph thu cừ ố ố ươ ụ ộ
vào quan h trong Zệp thì ph ng pháp đ ng cong elliptic phươ ườ ụ
thu c vào các nhóm xác đ nh trên các đ ng cong elliptic theoộ ị ườ
modulo n.
4.8.2. Thu t toán Dixon và sàng b c haiậ ậ
Thu t toán Dixon c xây d ng trên ýậ đượ ự
t ng n gi n mà ta ã th y trong h m tưở đơ ả đ ấ ệ ậ
Rabin. ý t ng ó là: n u tìm c x ưở đ ế đượ ≠ ±y
(mod n) sao cho x2≡y2 (mod n) thì UCLN(x-y,n)
là c không t m th ng c a n.ướ ầ ườ ủ
Ph ng pháp này s d ng ươ ử ụ c s nhân t ơ ở ử là
m t t p b ch a các s nguyên t bé. Tr c tiênộ ậ ứ ố ố ướ
ta nh n c m t vài s nguyên x sao cho t tậ đượ ộ ố ấ
c các th a s nguyên t c a xả ừ ố ố ủ 2 (mod n) n mằ
trong c s b (cách th c hi n i u này sơ ở ự ệ đ ề ẽ
c th o lu n sau). ý t ng th c hiên âyđượ ả ậ ưở ự ở đ
là l y tích c a m t vài giá tr sao cho m i sấ ủ ộ ĩ ỗ ố
nguyên t trong c s c s d ng m t số ơ ở đượ ử ụ ộ ố
ch n l n. i u này d n n m t ng d th cẵ ầ Đ ề ẫ đế ộ đồ ư ứ
d ng mong mu n xạ ố 2 ≡ y2 (mod n) mà ta hy v ngọ
s a n vi c phân tích n.ẽ đư đế ệ
Ta s minh ho b ng m t ví d ã c dẽ ạ ằ ộ ụ đ đượ ự
tính k l ng.ỹ ưỡ
Ví d 4.15ụ
Gi s n=15770708441(giá tr n này ã dùngả ử ị đ
trong ví d 4.14). Gi s b = {2,3,5,7,11,13}.ụ ả ử
Xét ba ng th c sau:đồ ứ
83409341562 ≡ 3 × 7 (mod n)
120449429442 ≡ 1 × 7 × 13 (mod n)
27737000112 =2 × 3 × 13 (mod n)
N u l y tích c a ba đ ng d th c trên:ế ấ ủ ồ ư ứ