# 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
end

p = get_prime
q = get_prime
n = p * q
e = 65537
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
else:
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
print(long_to_bytes(int(pow(c,d,n))).decode())


Executing it yields

True
SECCON{I_would_always_love_the_cryptography_and_I_know_RSA_never_gets_old_So_Im_always_a_fan_of_this_mathematical_magic_and...Wait_This_flag_can_be_longer_than_I_expected_What_happened?}


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