RSA暗号を手計算したくなること、ありますよね？？ (20260615_orestudy6_rsa)

2026年6月15日に開催された「俺の勉強会 #6」の発表資料です

https://ore-no-benkyoukai.connpass.com/event/394501/

#orestudy

Transcript

1. RSA暗号を 手計算したくなること、 ありますよね？？ Voicy ソフトウェアエンジニア 千田 航己 @thousanda
2. はじめに 2 某アニメ映画の主人公 「よろしくお願いしまぁぁぁすっ!!」 彼が世界を救うために解いていたのがRSA暗号です。 [1] [1] サマーウォーズの小磯 健二 (こいそ けんじ) くん
3. 今日のゴール この発表を聞いて分かりそうなこと ▪ 暗号/公開鍵暗号/RSA暗号 という技術の雰囲気 この発表を聞いても分からないこと ▪ 数学的な正確性 ▪ 具体的なアルゴリズム ▪ 情報セキュリティ全般の知識 3
4. 暗号 (cryptography) とは ▪ 意図した相手のみに情報を伝えるための技術 4 通信経路 メッセージ メッセージ 送信者 受信者
5. メッセージの盗聴 ▪ 意図した相手ではない攻撃者がメッセージを盗み見る 5 通信経路 メッセージ メッセージ 送信者 受信者 攻撃者 盗聴
6. メッセージの盗聴 ▪ 意図した相手ではない攻撃者がメッセージを盗み見る 6 通信経路 メッセージ メッセージ 送信者 受信者 攻撃者 盗聴 メッセージ 盗聴 成功
7. 暗号化 (encryption) ▪ メッセージ (平文) を、意味が読み取れない文章 (暗号文) に変換する 7 通信経路 送信者 平文 (plaintext) 暗号化 (encrypt) 暗号文 (ciphertext) 受信者
8. 暗号化 (encryption) ▪ メッセージ (平文) を、意味が読み取れない文章 (暗号文) に変換する 8 通信経路 暗号文 (ciphertext) 暗号文 (ciphertext) 送信者 受信者 攻撃者 盗聴
9. 暗号化 (encryption) ▪ メッセージ (平文) を、意味が読み取れない文章 (暗号文) に変換する 9 通信経路 暗号文 (ciphertext) 暗号文 (ciphertext) 送信者 受信者 攻撃者 盗聴 暗号文 (ciphertext) 内容 分からん
10. 復号 (decryption) ▪ 暗号文を平文に戻す 10 通信経路 暗号文 受信者 平文 (plaintext) 復号 (decrypt) 送信者
11. 鍵 ▪ 暗号化・復号するために必要な情報 11 通信経路 暗号文 (ciphertext) 暗号文 (ciphertext) 送信者 受信者 平文 (plaintext) 平文 (plaintext) 鍵 鍵
12. 公開鍵暗号とは ▪ 「暗号化に使う鍵」と「復号に使う鍵」が異なる ▪ 両方の鍵を、受信者が事前に作り、公開鍵を配る 12 公開鍵 (public key) 秘密鍵 (private key) 暗号文 (ciphertext) 暗号文 (ciphertext) 送信者 受信者 平文 (plaintext) 平文 (plaintext) 公開鍵で 暗号化 秘密鍵で 復号 送信
13. RSA暗号とは ▪ 公開鍵暗号のひとつ！ ▪ Rivest / Shamir / Adleman の3人が提唱した ▪ 「掛け算」と「素因数分解」の難しさの非対称性に依拠する手法 13
14. RSA暗号とは ▪ 公開鍵暗号のひとつ！ ▪ Rivest / Shamir / Adleman の3人が提唱した ▪ 「掛け算」と「素因数分解」の難しさの非対称性に依拠する手法。 ここで問題です。 「187」を素因数分解すると？ 14
15. RSA暗号とは ▪ 公開鍵暗号のひとつ！ ▪ Rivest / Shamir / Adleman の3人が提唱した ▪ 「掛け算」と「素因数分解」の難しさの非対称性に依拠する手法。 ここで問題です。 「187」を素因数分解すると？ では「11 x 17」は？ 15
16. 事前準備: 鍵生成 ▪ 2つ素数からnを用意します • p = 11 • q = 17 • → n = pq = 11 x 17 = 187 ▪ 鍵が決まります • e = 7 • d = 23 • ここで、eとdは e d ≡ 1 (mod (p-1)(q-1)) を満たす数の組み合わせ ▪ 公開鍵: (n, e) = (187, 7) ▪ 秘密鍵: (n, d) = (187, 23) 16
17. RSA暗号における暗号化 ▪ plaintext (送りたいメッセージ) を「5」とする ▪ 公開鍵: (n, e) = (187, 7) ▪ ciphertext = plaintext^e (mod n) • = 5^7 (mod 187) • = 5^4 x 5^3 • ≡ 64 x 125 • = 8000 • ≡ 146 (mod 187) => できあがった暗号文: 「146」 17 ここで、 5^4 = 625 ≡ 64 (mod 187)
18. RSA暗号における復号 ▪ 受け取った暗号文: 「146」 ▪ 秘密鍵: (n, d) = (187, 23) ▪ plaintext = ciphertext^d (mod n) • = 146^23 (mod 187) • = 146^(16+4+2+1) • ≡ 69 x 4 x (-2) x 146 • ≡ 5 (mod 187) => 復元された平文: 「5」 18 ここで、 146^2 = 21316 ≡ -2 (mod 187) 146^4 ≡ (-2)^2 = 4 (mod 187) 146^16 ≡ 4^4 = 256 ≡ 69 (mod 187)
19. RSA暗号の破り方 ▪ 公開鍵は持っています • (n, e) = (187, 7) ▪ nを構成する p, qを見つける 💡 • n = pq • 187 = pq • p = 11, q = 17 ▪ p, qが分かったので、dを計算します • ed ≡ 1 (mod (p-1)(q-1)) • d ≡ 187^(-1) (mod 160) • d ≡ 23 (mod 160) ▪ 秘密鍵ゲット！ : (187, 23) ▪ => あとはこれを使って通常通りの手順で復号すればよい 19 💡通常はこの素因数分解が めちゃくちゃ大変 サマーウォーズで 健二くんが解いていたのも この素因数分解！ (とされているはず)
20. むすび ▪ つまり、健二くんは攻撃者だったということです 20
21. Reference ▪ 映画「サマーウォーズ」公式サイト • https://s-wars.jp/ ▪ 『暗号技術のすべて』IPUSIRON 著 • https://www.shoeisha.co.jp/book/detail/9784798148816 ▪ いらすとや • https://www.irasutoya.com/ 21