30個の素数の中から2つランダムに選んで公開鍵を表示するプログラムが公開されており、それで暗号化したメッセージを解読する問題。公開鍵と暗号文はpcapファイルから読み取ることができるため、秘密鍵がわかれば復号可能なはず。
素数候補は30個しかないので、30*29/2=435パターンの鍵しか現れない。そのうち1つの公開鍵m=p*rで、使用された公開鍵n=p*qとすると、mとnの最大公約数gcd(m,n)がpとなるはずなので、そのようにpとq(=n/p)を探す。
いい感じのスクリプト書けなかったので、
for i in `seq 1 100`; do telnet ${target_url} 51818; done >> pubs.txt
で結果を集めて、余分な文を消した。100にしたのは適当。pが使われた公開鍵が1つでもあればいいので、100でも足りないかもしれないし、十分かもしれない。
import math
pub = 0xc20a1d8b3903e1864d14a4d1f32ce57e4665fc5683960d2f7c0f30d5d247f5fa264fa66b49e801943ab68be3d9a4b393ae22963888bf145f07101616e62e0db2b04644524516c966d8923acf12af049a1d9d6fe3e786763613ee9b8f541291dcf8f0ac9dccc5d47565ef332d466bc80dc5763f1b1139f14d3c0bae072725815f
# 約数の集合。pが含まれるはず。
pandq = set([])
with open("pubs.txt", "r") as file:
line = file.readline()
while line:
p = math.gcd(pub, int(line, 16))
if p != 1:
# 最大公約数が1以外であれば、OK
pandq.add(p)
line = file.readline()
print(pandq)
p = 12068007193924458934136437678747032125702047288192605563386647134926126290032925205587466786811951860570462107503408192389036293790565313661792631609456701とわかったので、q = pub // pでq = 11290942893206290336467162060839444758991526481896862143525109986063294905531141292368885863941910700698869187227122590028398079775349558555477255622057419とわかる。
l = (p-1)*(q-1)とすると、 e*d = 1 (mod l)となるらしい。すると、e*dがlの倍数+1ということなので、e*d + l*y = 1となる任意の整数yが存在するはず。eとlはわかっているので、この一次不等式は拡張ユークリッドの互除法で解くことができる。このあたりの説明は、以下のサイトなどで詳しく書いてある。
# 拡張ユークリッドの互除法
def ex_gcd(a, b):
if b == 0:
u = 1
v = 0
else:
q = a // b
r = a % b
(u0, v0) = ex_gcd(b, r)
u = v0
v = u0 - q * v0
return (u, v)
p = 12068007193924458934136437678747032125702047288192605563386647134926126290032925205587466786811951860570462107503408192389036293790565313661792631609456701
q = 11290942893206290336467162060839444758991526481896862143525109986063294905531141292368885863941910700698869187227122590028398079775349558555477255622057419
l = (p - 1)*(q - 1)
e = 65537
n = p*q
d = ex_gcd(e, l)[0]
# 値がマイナスの時は、lを足す
# 例：-8 ≡ 1 (mod 9) -> 10 ≡ 1 (mod 9)
if d < 0:
d += l
d=0x476f6f64207468696e67206e6f206f6e652063616e207265616420746869732120492764206861746520666f72207468656d20746f206b6e6f7720746861742074686520666c6167206973206d616b655f737572655f796f75725f726e675f67656e6572617465735f6c6f7473615f7072696d65732eとわかる。
秘密鍵dがわかったので、以下の式で復号。
enc = 0x49f573321bdb3ad0a78f0e0c7cd4f4aa2a6d5911c90540ddbbaf067c6aabaccde78c8ff70c5a4abe7d4efa19074a5249b2e6525a0168c0c49535bc993efb7e2c221f4f349a014477d4134f03413fd7241303e634499313034dbb4ac96606faed5de01e784f2706e85bf3e814f5f88027b8aeccf18c928821c9d2d830b5050a1e
pow(enc,d,n)
-> 0x476f6f64207468696e67206e6f206f6e652063616e207265616420746869732120492764206861746520666f72207468656d20746f206b6e6f7720746861742074686520666c6167206973206d616b655f737572655f796f75725f726e675f67656e6572617465735f6c6f7473615f7072696d65732e
これがASCIIコードになると思うけど、python3系でスマートに変換する方法がよくわからなかったので、わざわざpython2系で、
% python
>>> dec = 0x476f6f64207468696e67206e6f206f6e652063616e20726561642074686973212049276420686174652
0666f72207468656d20746f206b6e6f7720746861742074686520666c6167206973206d616b655f737572655f796f
75725f726e675f67656e6572617465735f6c6f7473615f7072696d65732e
>>> ("%x"%dec).decode('hex')
"Good thing no one can read this! I'd hate for them to know that the flag is make_sure_your_rng_generates_lotsa_primes."
として、変換。python3での変換方法は要調査。
python2系では、
>>> 35/2
17
と小数点以下切り捨てで整数となるが、python3系だと
>>> 35/2
17.5
と小数点となってしまい、計算しづらかった。
>>> 35//2
17
とすると、小数点以下切り捨てとなる。
どうでもいいけど、暗号文をコピーし間違えてて、気がつくのに時間がかかった。