rsa_understanding_memo

RSA暗号の暗号化/復号処理とその証明など
社内勉強会で話した内容からそのまま公開できない面白い要素を抜いたものです

1. RSA׬શཧղϝϞ 2021/11/26 ࣾ಺ษڧձ
2. ͸͡Ίʹ
3. ॾ஫ҙ • ࠓճ΍Δͷ͸͋͘·ͰૉͷRSA҉߸ʹ͍ͭͯͰ͢ɻPKCS#1 v1.5 ͱ͔ OAEP ͱ͔ͷ֤छpaddingํࣜʹ͍ͭͯ͸ݴٴ͠ͳ͍Ͱ͢ • ૉͷRSA͸͍͔ͭ͘ͷཧ༝ʹΑΓඇਪ঑ͳͷͰɺ࣮ࡍʹར༻͢Δͱ͖ ͸ރΕ࣮ͨ૷ͱ҆શͳpaddingΛ࢖͍·͠ΐ͏
4. RSAͥΜͥΜΘ͔ΒΜ • ͳΜ͔͍͍ײ͡ʹ҆શͬΆ͍҉߸Λͭͬͯ͘͘ΕΔͬΆ͍ • ͳΜ͔伴ͷbit͸௕͍΄͏͕ྑ͍Β͍͠ • ͳΜ͔ૉҼ਺෼ղ͕Ήͣͯ͘ΞϨΒ͍͠
5. ͥΜͥΜΘ͔Βͳ͍ͱࠔΔ͜ͱ • ҆શੑͷཧ༝͕Θ͔Βͳ͍(=ෳ਺ͷ҉߸ΞϧΰϦζϜؒͷ҆શੑͷൺ ֱ͕Ͱ͖ͳ͍) • ͥΜͥΜΘ͔Βͳ͍΋ͷʹഎதΛ༬͚Δͷ͸ͪΐͬͱ෺૽ɻݪཧΛ஌ Βͳ͍ͱෆ༻ҙʹةݥͳ͜ͱΛͯ͠͠·ͬͨΓͪ͠Ό͏͔΋
6. ͳͷͰ͍Ζ͍Ζௐ΂ͨ
7. ͷͰ΍͍ͬͯ͘
8. ࠓ೔΍Δ͜ͱ • RSAͷ҉߸Խ/෮߸ͷखॱͱ෮߸Ͱ͖Δ͜ͱͷূ໌ • ܻ਺͘͢ͳ͍RSAΛखܭࢉͰͱ͘ϋϯζΦϯ • ૉҼ਺෼ղͷࠔ೉ੑͱ҆શૉ਺ʹ͍ͭͯ • ΋ͬͱਂງΓ͍ͨਓ޲͚ͷRSAཧղͷͨΊͷϩʔυϚοϓ
9. RSAͷૢ࡞
10. ༻ҙ͢Δ΋ͷ • p, q Λ૬ҧͳૉ਺ͱͯ͠ n = pq ͱͳΔ੔਺ n • (p-1)(q-1) ͱޓ͍ʹૉͳ੔਺e • de ≡ 1 (mod (p-1)(q-1)) ͱͳΔ੔਺ d • n, eΛެ։伴ɺdΛൿີ伴ͱ͢Δ
11. ༻ҙ͢Δ΋ͷ • p, q Λ૬ҧͳૉ਺ͱͯ͠ n = pq ͱͳΔ੔਺ n • (p-1)(q-1) ͱޓ͍ʹૉͳ੔਺e • de ≡ 1 (mod (p-1)(q-1)) ͱͳΔ੔਺ d • n, eΛެ։伴ɺdΛൿີ伴ͱ͢Δ ͸΍͍͸΍͍͓͍ͪͭͯ
12. ༻ҙ͢Δ΋ͷ • p, q Λ૬ҧͳૉ਺ͱͯ͠ n = pq ͱͳΔ੔਺ n • (p-1)(q-1) ͱޓ͍ʹૉͳ੔਺e • de ≡ 1 (mod (p-1)(q-1)) ͱͳΔ੔਺ d • n, eΛެ։伴ɺdΛൿີ伴ͱ͢Δ Θ͔Δ
13. ༻ҙ͢Δ΋ͷ • p, q Λ૬ҧͳૉ਺ͱͯ͠ n = pq ͱͳΔ੔਺ n • (p-1)(q-1) ͱޓ͍ʹૉͳ੔਺e • de ≡ 1 (mod (p-1)(q-1)) ͱͳΔ੔਺ d • n, eΛެ։伴ɺdΛൿີ伴ͱ͢Δ ͓ޓ͍ૉͰͳʹ͕͏Ε͍͔͍ͬͯ͠͏ͱ࣍ ͷ৚݅ΛΈͨ͢E͕ଘࡏ͢Δ͜ͱ͕͍͑Δ͔ Β
    ༨ஊ͚ͩͲF͸ͱ͢Δ͜ͱ͕ଟ͍
    ͦͦ͜͜େ͖͍ૉ਺ͳͷͱɺਐ਺Ͱ ͱͳΓCJU͔͠ ͨͬͯͳͯ͘ԋࢉෛՙ͕͍ͪ͞ΊͳͨΊ
    
14. ༻ҙ͢Δ΋ͷ • p, q Λ૬ҧͳૉ਺ͱͯ͠ n = pq ͱͳΔ੔਺ n • (p-1)(q-1) ͱޓ͍ʹૉͳ੔਺e • de ≡ 1 (mod (p-1)(q-1)) ͱͳΔ੔਺ d • n, eΛެ։伴ɺdΛൿີ伴ͱ͢Δ NPE͸৒༨ΛٻΊΔॲཧͰɺϓϩάϥϜͰ ΍Δԋࢉͱಉ͡
    ৒༨ʹ͓͚Δ߹ಉ͸ӈͱࠨͷ৒༨͕౳͍͠ ͱ͍͏ҙຯ
    ͭ·ΓೃછΈ͋Δදݱʹ௚͢ͱ
    EF
    
    Q R
    
    
    
    Q R
    ͱͳ ΔE
    FΛ४උ͍ͤ΍ͱ͍͏͜ͱ
15. ༻ҙ͢Δ΋ͷ • p, q Λ૬ҧͳૉ਺ͱͯ͠ n = pq ͱͳΔ੔਺ n • (p-1)(q-1) ͱޓ͍ʹૉͳ੔਺e • de ≡ 1 (mod (p-1)(q-1)) ͱͳΔ੔਺ d • n, eΛެ։伴ɺdΛൿີ伴ͱ͢Δ NPE͸৒༨ΛٻΊΔॲཧͰɺϓϩάϥϜͰ ΍Δԋࢉͱಉ͡
    ৒༨ʹ͓͚Δ߹ಉ͸ӈͱࠨͷ৒༨͕౳͍͠ ͱ͍͏ҙຯ
    ͭ·ΓೃછΈ͋Δදݱʹ௚͢ͱ
    EF
    
    Q R
    
    
    
    Q R
    ͱͳ ΔE
    FΛ४උ͍ͤ΍ͱ͍͏͜ͱ EF
    㲇
    
    NPE
    Q R
    Λຬͨ͢EΛٻΊ Δͷ͸֦ுϢʔΫϦουޓআ๏Λ͔ͭ͑͹ ΘΓͱαΫοͱͰ͖Δ
    ֦ுϢʔΫϦουޓআ๏ͰͳΜͰ͏·͍͘ ͔͘͸ϕζʔͷ౳ࣜͱ͔ͱབྷΉͷͰׂѪ
    ڵຯ͋Δਓ޲͚ͷϩʔυϚοϓʹؔ܎ੑΛ ·ͱΊͱ͖·͢
16. ༻ҙ͢Δ΋ͷ • p, q Λ૬ҧͳૉ਺ͱͯ͠ n = pq ͱͳΔ੔਺ n • (p-1)(q-1) ͱޓ͍ʹૉͳ੔਺e • de ≡ 1 (mod (p-1)(q-1)) ͱͳΔ੔਺ d • n, eΛެ։伴ɺdΛൿີ伴ͱ͢Δ NPE͸৒༨ΛٻΊΔॲཧͰɺϓϩάϥϜͰ ΍Δԋࢉͱಉ͡
    ৒༨ʹ͓͚Δ߹ಉ͸ӈͱࠨͷ৒༨͕౳͍͠ ͱ͍͏ҙຯ
    ͭ·ΓೃછΈ͋Δදݱʹ௚͢ͱ
    EF
    
    Q R
    
    
    
    Q R
    ͱͳ ΔE
    FΛ४උ͍ͤ΍ͱ͍͏͜ͱ EF
    㲇
    
    NPE
    Q R
    Λຬͨ͢EΛٻΊ Δͷ͸֦ுϢʔΫϦουޓআ๏Λ͔ͭ͑͹ ΘΓͱαΫοͱͰ͖Δ
    ֦ுϢʔΫϦουޓআ๏ͰͳΜͰ͏·͍͘ ͔͘͸ϕζʔͷ౳ࣜͱ͔ͱབྷΉͷͰׂѪ
    ڵຯ͋Δਓ޲͚ͷϩʔυϚοϓʹؔ܎ੑΛ ·ͱΊͱ͖·͢ ͳΜͰͦΜͳ͜ͱ͢Δͷʁ
17. ͋ͱͰγϡͬͱͯ͠νϟͬͱ͢ΔΜͩΑʂ
18. ҉߸Խͷૢ࡞ • Ҏ߱͸ϓϨʔϯςΩετΛm, ҉߸ԽจࣈྻΛcͱ͠·͢ • RSAͷ҉߸Խ͸ Enc(m) := m^e mod n • Α͏͸mΛe৐ͯ͠%nͱΕ͹҉߸ԽͰ͖Δɻeͱn͸ެ։৘ใͳͷͰ୭ Ͱ΋҉߸ԽՄೳ
19. ෮߸ͷૢ࡞ • RSAͷ෮߸͸ Dec(c) := c^d mod n • ͜ΕͰmʹ΋ͲΔ • ͖ͬ͞ͷ෮߸ͱ͋Θͤͯ੔ཧ͢Δͱ (m^e mod n)^d mod n ͢Δͱm ʹ໭Δͱ͍͍ͬͯΔ • nΛ๏ͱ͢ΔmodͱΔૢ࡞͸్தͰ΍ͬͯ΋লུͯ͠΋݁Ռ͸͔ΘΒ ͳ͍ͷͰ (m^e)^d mod n ͱܭࢉͯ͠΋ಉ͡
20. ͨΊͯ͠ΈΑ͏ • m = (m^e mod n)^d mod n ͕੒Γཱͭͱͯ͠ܭࢉͯ͠ΈΔ • ద౰ʹn=35, e=5, d=5, m=4ͱ͔Ͱࢼͯ͠ΈΔ • m^e mod n = 4^5 mod 35 = 1024 mod 35 = 9 • c^d mod n = 9^5 mod 35 = 59049 mod 35 = 4 • 0 < m < n ͷൣғʹ͓͍ͯ੒ཱ͢Δ
21. (m^e)^d ≡ m (mod n) ͷূ໌(1) • ੔ཧͯ͠m^de ≡ m (mod n) • ͜͜Ͱ de ʹ͍ͭͯɺ de ≡ 1 (mod (p-1)(q-1)) ͱͳΔΑ͏ͳ਺͔ͩΒ ͳʹ͔͠Βͷ(p-1)(q-1)ͷഒ਺ʹ1଍ͨ͠஋Ͱ de = 1 + s(p-1)(q-1) ͱ ͔͚Δ • m^de = m^(1+s(p-1)(q-1)) = m(m^(p-1)(q-1))^s ͱ͔͚Δɻ͜ΕͰm ͷഒ਺ͷܗͰ͔͚ͨ
22. (m^e)^d ≡ m (mod n) ͷূ໌(2) • ·ͱΊΔͱ m(m^(p-1)(q-1))^s ≡ m (mod n) ͱͳΕ͹Α͍ • άοͱᛀΉͱ m^(p-1)(q-1) mod n ͕ͳʹ͔ͷखҧ͍Ͱ1ʹͳͬͯ͘Ε Δͱm(1)^s ≡ m (mod n) ͱͳͬͯ͘Εͦ͏ • ͦΜͳ౎߹ͷ͍͍͜ͱ…͋ΔΘ͚…͋ΔΘ͚…
23. (m^e)^d ≡ m (mod n) ͷূ໌(2) • ·ͱΊΔͱ m(m^(p-1)(q-1))^s ≡ m (mod n) ͱͳΕ͹Α͍ • άοͱᛀΉͱ m^(p-1)(q-1) mod n ͕ͳʹ͔ͷखҧ͍Ͱ1ʹͳͬͯ͘Ε Δͱm(1)^s ≡ m (mod n) ͱͳͬͯ͘Εͦ͏ • ͦΜͳ౎߹ͷ͍͍͜ͱ…͋ΔΘ͚…͋ΔΘ͚… େ਺ֶऀϑΣϧϚʔ ࢴ͕͘͢ͳ͍͜ͱͰ༗໊ ͋ΔͰ
24. ϑΣϧϚʔͷখఆཧ • p͸ૉ਺, a͸੔਺Ͱޓ͍ʹૉͱ͢Δͱ͖ҎԼ͕੒Γཱͭ • a^(p-1) ≡ 1 (mod p) • ূ໌΋঺հ͍͚ͨ͠Ͳۮવʹ΋खݩʹࢴ͕ແ͍ͷͰলུ͠·͢ • ͦͦ͜͜؆୯ͳͷͰ͕࣌ؒ༨ͬͨΒܰ͘঺հ͢Δ͔΋
25. (m^e)^d ≡ m (mod n) ͷূ໌(3) m^(p-1)(q-1) ≡ 1 (mod n) Λͱ͘ • ํ਑ͱͯ͠͸ͳΜ΍͔΍ͯ͠ m^(p-1)(q-1) -1 ≡ 0 (mod n) ͰׂΓ੾Ε Δ͜ͱΛ֬ೝ͢Δํ޲ͰؤுΔ • ↑͕੒Γཱͯ͹มܗͯ͠ m^(p-1)(q-1) ≡ 1 (mod n) ͕ٻ·Δ
26. (m^e)^d ≡ m (mod n) ͷূ໌(4) m^(p-1)(q-1) ≡ 1 (mod n) Λͱ͘ • (m^(p-1))^(q-1) ͱมܗͯ͠ߟ͑Δ • q͸ૉ਺͔ͩΒɺmࣗ਎͕qͷഒ਺Ͱͳ͍ݶΓ m^(p-1) ͱ͸ޓ͍ʹૉ ͳͷͰɺϑΣϧϚʔͷখఆཧΑΓ (m^(p-1))^(q-1) ≡ 1 (mod q) • ׂΓ੾ΕΔܗʹ੔ཧ͢Δͱ (m^(p-1))^(q-1) -1 ≡ 0 (mod q) • m^(p-1)(q-1) -1 ≡ 0 (mod q) ͕ࣔͤͨ … (i
27. (m^e)^d ≡ m (mod n) ͷূ໌(5) m^(p-1)(q-1) ≡ 1 (mod n) Λͱ͘ • (m^(q-1))^(p-1) ͱมܗͯ͠ߟ͑Δ • p͸ૉ਺͔ͩΒɺmࣗ਎͕pͷഒ਺Ͱͳ͍ݶΓ m^(q-1) ͱ͸ޓ͍ʹૉ ͳͷͰɺϑΣϧϚʔͷখఆཧΑΓ (m^(q-1))^(p-1) ≡ 1 (mod p) • ׂΓ੾ΕΔܗʹ੔ཧ͢Δͱ (m^(q-1))^(p-1) -1 ≡ 0 (mod p) • m^(p-1)(q-1) -1 ≡ 0 (mod p) ͕ࣔͤͨ … (ii
28. (m^e)^d ≡ m (mod n) ͷূ໌(6) m^(p-1)(q-1) ≡ 1 (mod n) Λͱ͘ • (i, (ii ΑΓ m^(p-1)(q-1) -1 ͸pͰ΋qͰ΋ׂΓ੾ΕΔ • p, q͸૬ҧͳૉ਺ͳͷͰ໿਺͕ଘࡏ͠ͳ͍ɻͦͷͨΊͲͪΒͰ΋ׂΓ ੾ΕΔͱ͍͏͜ͱ͸ m^(p-1)(q-1) -1 ͸ pq ͷഒ਺Ͱ͋Δ • Ҏ্ΑΓ m^(p-1)(q-1) -1 ≡ 0 (mod n) Ͱ͋Δ͜ͱ͕Θ͔Δ • มܗͯ͠ m^(p-1)(q-1) ≡ 1 (mod n) ͱͳΔʂ …(iii
29. (m^e)^d ≡ m (mod n) ͷূ໌(7) • m(m^(p-1)(q-1))^s ≡ m (mod n) ͱͳΕ͹Α͍ • άοͱᛀΉͱ m^(p-1)(q-1) mod n ͕ͳʹ͔ͷखҧ͍Ͱ1ʹͳͬͯ͘ΕΔͱ m(1)^s ≡ m (mod n) ͱͳͬͯ͘Εͦ͏ • pqͱޓ͍ʹૉͳmͳΒ m^(p-1)(q-1) ≡ 1 (mod n) ͱͳΔͷͰˢ͕੒ཱ͢Δʂূ ໌͓ΘΓ • ͪͳΈʹpqͱm͕ૉ͡Όͳ͍ͱ͖͸ϑΣϧϚʔͷখఆཧͱ͔ߟ͑ͳͯ͘Αͯ͘ m͕p, qͰׂΓ੾ΕΔ͜ͱΛར༻ͯ͠୯ʹnͷഒ਺+mͷܗʹ੔ཧͰ͖Δ
30. खܭࢉͰͱͧ͘ʂ
31. ໰୊ • 1~26ͷ਺ࣈΛͦΕͧΕΞϧϑΝϕοτͷA~ZʹׂΓ౰ͯͨՍۭͷจ ࣈίʔυ͕ଘࡏ͢Δͱ͢Δ • n=35, e=5 ͕Θ͔͍ͬͯΔͱ͖ɺҎԼͷ3ͭͷ҉߸จΛղಡͯ͠Ͷ • 23, 24, 1
32. ໰୊ • 1~26ͷ਺ࣈΛͦΕͧΕΞϧϑΝϕοτͷA~ZʹׂΓ౰ͯͨՍۭͷจ ࣈίʔυ͕ଘࡏ͢Δͱ͢Δ • n=35, e=5 ͕Θ͔͍ͬͯΔͱ͖ɺҎԼͷ3ͭͷ҉߸จΛղಡͯ͠Ͷ • 23, 24, 1 • ώϯτ1: c^d mod n Ͱ෮߸Ͱ͖Δɻd͸ de ≡ 1 (mod (p-1)(q-1)) • ώϯτ2: n = pq ͱͳΔpqʹૉҼ਺෼ղͰ͖Ε͹͋ͱ͸ܭࢉ͢Δ͚ͩ
33. ͨ͑͜ • n ͸35͔ͩΒୈ࿡ײͰ 5 * 7 ͷૉҼ਺෼ղͰ͖Δ • Αͬͯd͸ 5d ≡ 1 mod (5 - 1)(7 - 1) • ܭࢉ͢Δͱ5d - 1 ≡ 0 mod 24 ͱͳΓɺd = 5 ͕͋ͯ͸·Δ͜ͱ͕Θ͔Δ • ͋ͱ͸ 23^5 mod 35, 24^5 mod 35, 1^5 mod 35 ΛٻΊΔ͚ͩɻखͰ΍Δ ͱ͖͍͚ͭͲΪϦࠜੑͰղ͚Δൣғ • ղ͘ͱ 18, 19, 1 ʹͳͬͯṖͷจࣈίʔυʹরΒ͠߹ΘͤΔͱ RSA ʹͳΔʂ
34. ϋϯζΦϯ͔ΒΘ͔Δ͜ͱ • ૉҼ਺෼ղ͑͞Ͱ͖ͨΒޙ͸ܭࢉ͢Δ͚ͩ • ୯७ܭࢉ͸ίϯϐϡʔλͷಘҙͱ͢Δͱ͜ΖͳͷͰͦ͜·Ͱ͍͚͹ νϣϩ͍ • RSAͷ೉͠͞͸ૉҼ਺෼ղͷࠔ೉͞ʹґڌ͍ͯ͠Δɻ͕͜͜ಥഁ͞Ε Δͱγϡοͱൿີ伴͕ܭࢉ͞ΕͪΌ͏
35. ૉҼ਺෼ղͷࠔ೉ੑͱ҆શૉ਺
36. ૉҼ਺෼ղ͖ͪʔͧʂ • ଟ߲ࣜ࣌ؒͰͱ͚ΔΞϧΰϦζϜΈ͔ͭͬͯͳ͍ͷ… • ࢦ਺͔͔࣌ؒΔ͔ΒͭΒ͍ͷ… • ର৅ͱͳΔૉ਺ͷܻ͕૿͑Ε͹૿͑Δ΄ͲΞϗΈ͍ͨʹ͔͔࣌ؒΔ • 200ܻ * 200ܻ͙Β͍ͩͱ͍·ͷεύίϯͰ΋਺ԯ೥͔͔ΔΑ͏Ͱ͢ (ࢦ਺͔͔࣌ؒΔͱ͍͏ͱ͜Ζ·Ͱ͔͠௥ͬͯͳ͍͔ΒͲ͏͍͏ܭࢉ Ͱ਺ԯ೥ͱ͍ͬͯΔͷ͔͸஌Βͳ͍)
37. ૉҼ਺෼ղޮ཰Α͘Ͱ͖ͳ͍ʁ • p-1๏ͱ͍͏ͷ͕͋Δ • ͘Θ͘͠͸๻΋௥͍͔͚Εͯͳ͍͚ͲɺϑΣϧϚʔͷখఆཧΛ͔ͭͬ ͨߟ͑ํͰɺૉ਺p͔Β-1ͨ͠ͱ͖ʹখ͞ͳૉ਺Ͳ͏͠ͷੵʹͳͬͯ Δͱޮ཰Α͘ܭࢉͰ͖ΔΒ͍͠ • Ͱ͔͍ૉҼ਺͕;͘·ΕͯΔͱp-1๏͸ޮ཰Α͘Ͱ͖ͳ͍
38. ҆શૉ਺ͱ͸ • p, qͷ૬ҧͳૉ਺͕͋ͬͨͱ͖ p = 2q +1 ͱͳΔૉ਺ • p-1๏͸p-1ʹͰ͔͍ૉҼ਺͕͋Δͱޮ཰͕͋Βͳ͍ͷΛࢥ͍ग़͢ͱɺ҆શ ૉ਺͸p-1๏ʹͱ͔ͬͯͳΓ૬खͨ͘͠ͳ͍਺(p-1ͷૉҼ਺ʹ͍͍ͩͨp/2 ͷαΠζͷόΧσΧૉ਺͕͋ΔͷͰ) • ҉߸తͳڧ౓Λ΋ͭૉ਺ੜ੒ͱ͸ɺे෼େ͖͍҆શૉ਺Λͭͬͯ͘͘ΕΔ ͬͯ͜ͱͩͧʂ͜͜ςετʹग़·͢ • े෼ͳܻ਺ͷ҆શૉ਺ͷੵ͸·͋ૉҼ਺෼ղ͢Δͷແཧ΍Ζͱͳ͍ͬͯΔ
39. ਂງΓ͍ͨਓ޲͚ RSAཧղ΁ͷϩʔυϚοϓ
40. ҉߸Խ/෮߸͕੒ཱ͢Δ͜ͱ Λཧղ͢ΔͨΊʹඞཁͬΆ͍΍ͭ • ϑΣϧϚʔͷখఆཧ • ؆୯Ί • ΦΠϥʔͷఆཧ • ϑΣϧϚʔͷఆཧ͸๏p͕ૉ਺Ͱ͋Δඞཁ͕͚͋ͬͨͲɺͦΕΛҰ ൠʹ֦ுͯ͠ޓ͍ʹૉͳa, nͰ͋Ε͹੒ཱ͢ΔΑ͏ʹͨ͠΍ͭ • ͜ΕͰূ໌ͯ͠Δ͜ͱ΋ଟ͍͚ͲϑΣϧϚʔͷখఆཧͱେମ͓ͳ͡
41. de ≡ 1 (mod (p-1)(q-1)) ΛٻΊΔํ๏ ͷཧղʹඞཁͬΆ͍΍ͭ • ܈, ؀, ମͷݴ༿ͷఆٛ͘Β͍ • ͷͪͷূ໌ʹ͠Εͬͱग़͖ͯͯͳΜͩ͜ΕͱͳΔ • ୯Ґݩ, ٯݩ͋ͨΓ΋ݴ༿ͷҙຯ͕Θ͔ΔͱΑ͛͞ • ϕζʔͷ౳ࣜ • ax+by=c͕࣮਺ղΛ࣋ͭͳΒc͸gcd(a,b)ͷഒ਺ͩͧͱ͍͏΍ͭɻݸਓతʹ͸ࠓճಡΜͩূ໌ͰҰ൪Ή͔ͣͬͨ • ϢʔΫϦουޓআ๏ • gcd(a,b)Λޮ཰Α͘΋ͱΊΔΞϧΰϦζϜɻ͜Ε΋ূ໌͕؆୯ • ֦ுϢʔΫϦουޓআ๏ • ϕζʔͷ౳ࣜΛຬͨ͢ղΛ୳ࡧͰ͖Δɻ࣮૷ͱͯ͠͸ϢʔΫϦουޓআ๏ʹໟ͕ੜ͑ͨఔ౓ • ͍ͭ͜Ͱ৒༨؀ͷٯݩ͕ͩͤΔઆ໌͸ผ్ಡ·ͳ͍ͱΘ͔Β͵͔΋
42. ҆શͳn=pqΛ࡞Δํ๏ ͷཧղʹඞཁͬΆ͍΍ͭ • ૉ਺ੜ੒ΞϧΰϦζϜ͸ਖ਼௚͓͍͖Εͯͳ͍ • ద౰ͳૉ਺ͬΆ͍਺ͭ͘Δ -> ߴ଎ͳૉ਺൑ఆʂͷྲྀΕ͕͓͓͍ɻߴ଎ͳૉ ਺൑ఆ͸֬཰తͳΞϧΰϦζϜ͹͔ͬΓ͔ͩΒෳ਺ճ܁Γฦͯ͠ޡݕ஌཰Λ ͛͞Δ(n=10ͱ͔) • Miller-Rabin๏: ૉ਺͡Όͳ͍਺ʹOKग़ͪ͠Ό͏ͷ͸25%ҎԼ • Baillie-PSW๏: ͍͔ͭ͘ͷૉ਺൑ఆΞϧΰϦζϜΛ૊Έ߹Θͤͯຐվ଄ͨ͠ Έ͍ͨͳ΍ͭʁͪΌΜͱ௥ͬͯͳ͍͚ͲGoͱ͔Ͱ࢖ΘΕͯΔ͔ΒΑͦ͞͏
43. ҆શͳn=pqΛ࡞Δํ๏ ͷཧղʹඞཁͬΆ͍΍ͭ • ૉ਺ੜ੒ΞϧΰϦζϜ͸ਖ਼௚͓͍͖Εͯͳ͍ • ద౰ͳૉ਺ͬΆ͍਺ͭ͘Δ -> ߴ଎ͳૉ਺൑ఆʂͷྲྀΕ͕͓͓͍ɻߴ଎ͳૉ ਺൑ఆ͸֬཰తͳΞϧΰϦζϜ͹͔ͬΓ͔ͩΒෳ਺ճ܁Γฦͯ͠ޡݕ஌཰Λ ͛͞Δ(n=10ͱ͔) • Miller-Rabin๏: ૉ਺͡Όͳ͍਺ʹOKग़ͪ͠Ό͏ͷ͸25%ҎԼ • Baillie-PSW๏: ͍͔ͭ͘ͷૉ਺൑ఆΞϧΰϦζϜΛ૊Έ߹Θͤͯຐվ଄ͨ͠ Έ͍ͨͳ΍ͭʁͪΌΜͱ௥ͬͯͳ͍͚ͲGoͱ͔Ͱ࢖ΘΕͯΔ͔ΒΑͦ͞͏ ͪͳΈʹ҆શૉ਺ͷੜ੒ʹ͍ͭͯ͸͋Μ· Γ͏·͘΍ͬͯͳ͍ؾ͕͍ͯͯ͠ɺ
    ૉ௚ʹ೚ҙͷૉ਺൑ఆͰૉ਺RΛͭͬͨ͘ޙ R ͕ૉ਺͔͓͔ΘΓ൑ఆͯ͠ૉ਺ͩͬͨ Β͍ͦͭΛQͱͯ͠ฦ͢Έ͍ͨͳงғؾ͕͋ Δ
    ͪΌΜͱௐ΂͖Εͯͳ͍͚Ͳ௚ײతʹ΋ͦ Ε͕ૣͦ͏
44. RSAʹ͍ͭͯͷઆ໌͸ ͜Εʹͯऴྃ
45. ׬