Created
July 6, 2016 09:13
-
-
Save sonickun/0e9c9cda6a5867edd8f8b0d108001d65 to your computer and use it in GitHub Desktop.
SECCON CTF 2015 Online Quals Find the prime numbers (Crypto 200pt)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# SECCON CTF 2015 Online Quals Find the prime numbers (Crypto 200pt) | |
def egcd(a, b): | |
if (a == 0): | |
return [b, 0, 1] | |
else: | |
g, y, x = egcd(b % a, a) | |
return [g, x - (b // a) * y, y] | |
# Modular multiplicative inverse | |
def modInv(a, m): | |
g, x, y = egcd(a, m) | |
if (g != 1): | |
raise Exception("[-]No modular multiplicative inverse of %d under modulus %d" % (a, m)) | |
else: | |
return x % m | |
def L(u, n): | |
return (u - 1) / n | |
# c + o = h | |
# 2312852200158242541 + 3960472713339509644 = 1680683066780585790 | |
c = 2312852200158242541 | |
o = 3960472713339509644 | |
h = 1680683066780585790 | |
# h = o * c mod n^2 | |
# Get factors of "o*c-h" | |
# 2 * 3^3 * 42727^2 * 58757^2 * 664253 * 40517588857 | |
p = 42727 | |
q = 58757 | |
n = p * q | |
ramda = (p - 1) * (q - 1) | |
l = pow(c, ramda, n * n) | |
# g = 1 + n (mod n^2) | |
# mu = L(g^ramda mod n^2) (mod n) | |
# = ramda (mod n) | |
ramda_inv = modInv(ramda, n) | |
m = (L(l, n) * ramda_inv) % n | |
print m | |
# Result | |
# > python solver.py | |
# 1510490612 | |
# Access: http://paillar.quals.seccon.jp/cgi-bin/pq.cgi?1510490612 | |
# Flag: SECCON{SECCoooo_oooOooo_ooooooooN} |
The Flag is "SECCON{SECCoooo_oooOooo_ooooooooN}" :)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
とある暗号の実装と暗号文を含む3数が与えられる。実装から加法準同型暗号の一つであるPaillier暗号だと分かる。3数の定義より素因数分解を用いて秘密鍵の候補となる素数が計算できる(複数のデータセットを用いて特定)。後はPaillierの復号方法に則ってコードを書き平文を求める。