RSA暗号
RSA暗号とは
1977年にリベスト（Rivest）、シャミア(Shamir)、エーデルマン（Adleman）が提唱した。公開鍵暗号の１つ。
RSA暗号を理解するための数学知識
最大公約数 ユークリッドの互除法 拡張ユークリッドの互除法 整数の合同 合同式の逆元 既約剰余類 オイラー関数 フェルマーの小定理
CTFから見たRSA暗号への攻撃方法
Wiener's Attack
eの値が大きい時に成立
Boneh-Durfee's low private exponent Attack
eの値が小さい時に成立
weak rsa
Common Modulus Attack
同一の平文を異なるeで暗号化した暗号文があるときに成立。
Common Private Exponent Attack
Franklin-Reiter Related Message Attack
暗号文c1、c2を持ち、それに対する平文がm1、m2の上位ビットが共通するとき成立。
このとき
m2=a*m1 + b が分かり、・・・
Coppersmith's Attack
素数pの上位ビットまたは下位ビットが分かる時に成立。
秘密鍵dの下位ビットが分かるとき成立。
平文ｍの上位ビットまたは下位ビットが分かる時に成立。
Coppersmith's short pad Attack
Partial-key exposure Attack / High-bit known Attack
Haste'd Broadcast Attack
同一の平文を異なるnで暗号化した暗号文があるときに成立。中国人剰余定理を用いることで平文mが求まる。
LSB Decryption Oracle Attack
任意の暗号文を復号した結果の偶奇（下位１bit）が分かるときに成立。
ｍの偶奇が分かるので、二分探索によってｍが求まる。
RSA暗号における各値の一般的な値
e=65537(0x10001) or 3
これはバイナリ・ユークリッドの互除法を用いて高速化しやすいために選ばれている。
N
2048ビット以上。512ビットぐらいだとECMを利用して1分程度で素因数分解できるらしい。
Tool
pythonの各種モジュール
factordb.com
素数のデータベース(素因数分解してくれる!)
http://www.factordb.com/
参考文献
暗号技術のすべて：IPUSIRON（著）
暗号技術入門：結城浩（著）
「CTF Crypto」
https://raintrees.net/projects/a-painter-and-a-black-cat/wiki/CTF_Crypto#RSA%E6%9A%97%E5%8F%B7
