[ISITDTU 2018] Simple RSA Write-up

from Crypto.Util.number import *
import random
flag = 'Hidden'
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)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        #raise Exception('modular inverse does not exist')
        print "aaa"
    else:
        return x % m
def next_prime(n):
    num = n + 1
    while True:
        if isPrime(num):
            return num
        num += 1
p = random.randint(1<<251,1<<252)
i = 10
p = next_prime(p)
p1 = next_prime(p*10)
p2 = next_prime(p1*10)
p3 = next_prime(p2*10)
 
 
 
N = p*p1*p2*p3
e = 65537
c = pow(bytes_to_long(flag),e,N)
print c
#153348390614662968396805701018941225929976855876673665545678808357493865670852637784454103632206407687489178974011663144922612614936251484669376715328818177626125051048699207156003563901638883835345344061093282392322541967439067639713967480376436913225761668591305793224841429397848597912616509823391639856132
print N
#603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231

문제입니다. 정말 심플합니다. modinv()함수까지 다 짜주어서 그냥 p,p1,p2,p3만 구하면 문제를 풀 수 있습니다.

물론 그게 어렸기 때문에 고생하는 거지만요 ㅠㅠ

그래서 저는 저걸 못구해서 끙끙거렸는데;;

이걸 같이 CTF하는 팀원님이 구해주셨습니다(대단해...!! rls1004님 감사합니당...)

저는 이걸 p를 gmpy.root(N/1000000,4)로 해서 잡아놓고 1씩 올리거나 내리면서 계산햇는데;; ㅠㅠ

알고리즘 공부를 더 해야할거같습니다 ㅠㅠ

대회가 끝나고 다른분들 writeup을 보니 이진탐색도 사용하더군엽.. 

p를 N/1000000의 4제곱근 근처로 잡은 이유는 문제코드가 아래와 같아서 입니다.

p = next_prime(p) p1 = next_prime(p*10) p2 = next_prime(p1*10) p3 = next_prime(p2*10)

즉... N=p*(p*10+a)*(p*100+b)*(p*1000+c) 일테니..

대충 p^4 * 1000000 + A 일겁니다. 그러므로 .root(N/1000000,4)로 잡아놓고 풀었습니다.

from Crypto.Util.number import *
import gmpy
 
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)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        #raise Exception('modular inverse does not exist')
        print "aaa"
    else:
        return x % m
 
def next_prime(n):
    num = n + 1
    while True:
        if isPrime(num):
            return num
        num += 1
 
N = 603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231
e = 65537
 
start, perfect  = gmpy.root(N/1000000,4)
a = 0x1000
b = 0xf
while a != 0:
    p = start + a * b
    p = next_prime(p)
    p1 = next_prime(p*10)
    p2 = next_prime(p1*10)
    p3 = next_prime(p2*10)
 
    tmp = p*p1*p2*p3
 
    if tmp == N:
        print p, p1, p2, p3
        break
    if tmp > N:
        b -= 1
    else:
        start = start + a * b
        print hex(start)
        a = a/0x10
        b = 0xf
"""
p  = 4955491002253862893875866857920361781272456756179979954923353247500965791683
p1 = 49554910022538628938758668579203617812724567561799799549233532475009657916989
p2 = 495549100225386289387586685792036178127245675617997995492335324750096579170109
p3 = 4955491002253862893875866857920361781272456756179979954923353247500965791701557
"""
if(p*p1*p2*p3 == N):
    print("great!")
    
phi = (p-1)*(p1-1)*(p2-1)*(p3-1)
d = modinv(e, phi)
 
c = 153348390614662968396805701018941225929976855876673665545678808357493865670852637784454103632206407687489178974011663144922612614936251484669376715328818177626125051048699207156003563901638883835345344061093282392322541967439067639713967480376436913225761668591305793224841429397848597912616509823391639856132
 
dec = pow(c,d,N)
print(long_to_bytes(dec))
 
 
 

참고로 python 모듈이 없다면, sage로도 가능!

N = 603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231
print("start")
tmp = isqrt(N/1000000)
tmp = isqrt(tmp)
print(tmp)

http://math3.skku.ac.kr/home/myriabreak/7/