home - links - about - /git/ - rss

Seccon 2020 - This Is RSA [EN]

This is RSA

This was a warmup crypto challenge at Seccon CTF 2020. We are given a script, rsa.rb, containing the following ruby code:

require 'openssl'

def get_prime
  i = OpenSSL::BN.rand(512).to_s.unpack1('H*').hex
  OpenSSL::BN.new(i).prime? ? i : get_prime

p = get_prime
q = get_prime
n = p * q
e = 65537
m = File.read('flag.txt').unpack1('H*').hex
c = m.pow(e, n)

puts "N = #{n}"
puts "c = #{c}"

We are also given a trace of execution.

N = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657
c = 9094564357254217771457579638296343398667095069849711922513911147179424647045593821415928967849073271368133854458732106409023539482401316282328817488781771665657515880026432487444729168909088425021111879152492812216384426360971681055941907554538267523250780508925995498013624610554177330113234686073838491261974164065812534037687990653834520243512128393881497418722817552604416319729143988970277812550536939775865310487081108925130229024749287074763499871216498398695877450736179371920963283041212502898938555288461797406895266037211533065670904218278235604002573401193114111627382958428536968266964975362791704067660270952933411608299947663325963289383426020609754934510085150774508301734516652467839087341415815719569669955613063226205647580528

As i'm not really familiar with Ruby, it took me way too long to notice that the get_prime function does some strange string and hex conversions. In fact, one can translates it to the following equivalent python code:

def get_prime():
    i = int.from_bytes(str(random.getrandbits(512)).encode(), byteorder='big')
    if is_prime(i):
        return i
        return get_prime()

That means that the primes generated by the function can be converted from long to bytes, and the bytes decoded to a string that will represent a valid decimal integer.

More formally, the primes are of the form \(p = \sum\limits_{i = 0}^{l} p_i \times 16^{2i}\), with \(l = \lceil \log_{10} 2^{512} \rceil = 155\) and where each \(p_i\) is the ascii code of a digit, ie \(p_i \in \{48,..,57\}\).

By writing \(p \times q = (\sum\limits_{i = 0}^{l} p_i \times b^i) \times (\sum\limits_{i = 0}^{l} q_i \times b^i) = \sum\limits_{i = 0}^{2l} n_i \times b^i\) in base \(b = 16^2\), the factorisation is relatively easy to do.

One can notice that as for \(i \in \{0,..,l\}, n_i = \sum\limits_{k = 0}^i p_k \times q_{i - k}\) and as each \(p_i,q_i\) can have only ten different values, its easy to iteratively guess the values of \(p_i\) and \(q_i\) by checking for the equality.

Here is a sage script that implements that idea:

n = [...]
c = [...]
e = 65537
b = 16**2

P = PolynomialRing(ZZ, 'x')
ni = Integer(n).digits(b)

def get_coeff(pc, qc, deg):

    ni_wanted = ni[deg]

    for pi in range(0x30,0x3a):
        for qi in range(0x30,0x3a):

            p1 = P(pc + [pi])
            p2 = P(qc + [qi])

            ni_guess = (p1*p2)(b).digits(b)[deg]

            if ni_guess == ni_wanted:
                pc = pc + [pi]
                qc = qc + [qi]
                return pc,qc

pc,qc = [],[] # list of p and q coeffs
for deg in range(155):
    pc,qc = get_coeff(pc, qc, deg)

p = sum(x*b**i for i,x in enumerate(pc))
q = sum(x*b**i for i,x in enumerate(qc))

print(n == p*q)
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)

from Crypto.Util.number import long_to_bytes

Executing it yields


This is probably not the best algorithm to factor in this case, but hey this is CTF code and it works ^^

Creative Commons License