RSA暗号の問題を実装してみた

前回の続きで、早速問題(一部除く)を作ってみました。
前回の記事はこちらをご覧ください。

環境
Python 3.11.1
sympy 1.12
gmpy2 2.1.5

目次

• Low Public Exponent Attack
• wiener's attack(できなかった)
• 素因数分解で素数特定可能
• まとめ
• 参考文献

Low Public Exponent Attack

import sympy
import gmpy2
p = sympy.randprime(10 ** 99, 10 ** 100)
q = sympy.randprime(10 ** 99, 10 ** 100)
n = p*q
e = 3
l = (p-1)*(q-1)
d = gmpy2.invert(e,l)
message = b'Hello'
m = int.from_bytes(message, "big")
c = pow(m,e,n)
print('n:', n)
print('c:', c)
print('e:', e)

wiener's attack(できなかった)

何度も実装してみたけどdが短くなるようにうまく行きませんでした、、、
何故かe大きくしても相対的にdが小さくならない・・・?

素因数分解で素数特定可能

計算量がO(N)の場合、10^8までは約1秒で求められることを利用したものです。

import sympy
import gmpy2
p = sympy.randprime(10 ** 7, 10 ** 8)
q = sympy.randprime(10 ** 100, 10 ** 200)
n = p*q
e = 65537
l = (p-1)*(q-1)
d = gmpy2.invert(e,l)
message = b'Hello'
m = int.from_bytes(message, "big")
c = pow(m,e,n)
print('n:', n)
print('c:', c)
print('e:', e)

まとめ

問題が解けるものがあっても作問ができるとは限らないとなると、
CTFの作問者の人って本当にすごい・・・

参考文献

IPFactory Advent Calender 2023

5日目 im_yappiさん

7日目 ERUTONEさん