[Crypto] Serifin

This is a puzzle from the ASIS CTF Final 2019.

The first crypto puzzle we solved was Serifin. We were given N=pqN = pq, a product of two primes, and c=m3(modN)c = m^3 \pmod{N} where mm is our message. This is a RSA-like construction, and our first goal was to factorize N.N.

N = 420908150499931060459278096327098138187098413066337803068086719915371572799398579907099206882673150969295710355168269114763450250269978036896492091647087033643409285987088104286084134380067603342891743645230429893458468679597440933612118398950431574177624142313058494887351382310900902645184808573011083971351;
c = 78643169701772559588799235367819734778096402374604527417084323620408059019575192358078539818358733737255857476385895538384775148891045101302925145675409962992412316886938945993724412615232830803246511441681246452297825709122570818987869680882524715843237380910432586361889181947636507663665579725822511143923;
0.5s
Julia
Julia 1.2

In general, this is hard. Fortunately, we were given the method where pp and qq were constructed.

def serifin(a, l):
    S, s = a, a
    while True:
        S += float(a)/float(l)
        if S - s < .0001:
            return int(S) + 1
        else:
            s, a = S, float(a)/float(l)
def genPrime(nbit):
    while True:
        p = getPrime(512)
        if p % 9 == 1 and p % 27 >= 2:
            q = gmpy2.next_prime(serifin(p, 3) + serifin(p, 9) + serifin(p, 27))
            if q % 9 == 1 and q % 27 >= 2:
                return int(p), int(q)
Method of generating primes
Python

We made a wrong step initially, and assumed serifin⁡(a,l)=⌈lal−1⌉.\operatorname{serifin}(a,l) = \lceil \frac{la}{l-1} \rceil. Then, we can obtain qq from pp by

q(p)=next_prime⁡(⌈3p2⌉+⌈9p8⌉+⌈27p26⌉).q(p) = \operatorname{next\_prime}\left(\left\lceil \frac{3p}{2} \right\rceil + \left\lceil \frac{9p}{8} \right\rceil + \left\lceil \frac{27p}{26} \right\rceil\right).

As q(p+1)≥q(p),q(p+1) \geq q(p), we can perform a binary search as follows. We guess a p0p_0 and compute N0=p0⋅q(p0).N_0= p_0 \cdot q(p_0). If N>N0,N > N_0, we need to increase p0.p_0. Similarly, if N<N0,N < N_0, we need to decrease p0.p_0.

Did you spot our bug? We neglected the floating point rounding of Python. Fortunately, the idea that qq is generated from pp and qq increases if and only if pp increases still hold. Thus, we can perform the following binary search.

using Pkg; Pkg.add("Primes");
using Primes
1.5s
Julia
Julia 1.2
# Conversion of Serifin to Julia
function Serifin(a, l)
  S = s = a
  while true
    S += convert(Float64, a)/convert(Float64, l)
    S = convert(Float64, S)
    S - s < .0001 && return convert(BigInt, floor(S)) + 1
    s, a = S, convert(Float64, a)/convert(Float64, l)
  end
end
# Compute q_of(p) given p
q_of(p) = nextprime(Serifin(p,3) + Serifin(p, 9) + Serifin(p, 27))
function BinSearch(N)
  Low = big(1)
  # As we are searching for a prime factor of N, one of them is at most sqrt(N)
  High = big(convert(BigInt, floor(sqrt(N)))) 
  
  while High - Low > 1 # The answer lies in [Low, High)
    p0 = (Low + High) ÷ 2
    N0 = p0*q_of(p0)
    if N0 > N
      High = p0
    else
      Low = p0
    end
  end
  
  return Low
end
p = BinSearch(N); q = N ÷ p;
println("p = $p")
println("q = $q")
5.3s
Julia
Julia 1.2

Now we have obtained pp and q,q, our final step is to find m.m. The standard procedure is to compute the following constants.

mp3≡c(modp)mq3≡c(modq)\begin{aligned} m_p^3 &\equiv c \pmod{p} \\ m_q^3 &\equiv c \pmod{q} \\ \end{aligned}

Next, we compute p′p' such that 3p′≡1(modp−1),3p' \equiv 1 \pmod{p-1}, yielding

(mp3)p′≡mp3p′≡mp(modp),(m_p^3)^{p'}\equiv m_p^{3p'} \equiv m_p \pmod{p},

where the last equality is due to Fermat's Little Theorem. We do the same thing for qq and use Chinese Remainder Theorem to reconstruct m.m. We run into a slight problem here! The values p′p' and q′q' do not exist as the greatest common divisors gcd⁡(3,p−1)=gcd⁡(3,q−1)=3.\gcd(3, p - 1) = \gcd(3, q - 1) = 3. Fortunately, not all hope is lost. We can attempt to factorise x3−mp3x^3 - m^3_p in Fp[x].F_p[x]. 

Pkg.add("Nemo")
using Nemo
1.1s
Julia
Julia 1.2
F, _ = FiniteField(p, 1, "a") # Creates a Finite Field of p^1
R, x = PolynomialRing(F, "x")
PossibleMp = [p - parse(BigInt, string(evaluate(i, 0))) for (i, _) in Nemo.factor(x^3 - c)]
0.7s
Julia
Julia 1.2
3-element Array{BigInt,1}: 1915332594464015724876880553736057618778455894353099778049534670817405343574755905220882080642399997438470451580925301802728865937271850867184921170924039 247001095059170766068890790031433905641180386308800796995551675796399284638799044302762442484201220553803716601201181837866586006737963255424921207622978 8556507823954719328174286803368355713871729081931820100591167424469189115575188134292472883975137368001711338465567891806689776267142082582573600219226762

This gives us three possibilities for mp,m_p, and we can do similarly for mq.m_q.

F, _ = FiniteField(q, 1, "a")
R, x = PolynomialRing(F, "x")
PossibleMq = [q - parse(BigInt, string(evaluate(i, 0))) for (i, _) in Nemo.factor(x^3 - c)]
0.6s
Julia
Julia 1.2
3-element Array{BigInt,1}: 15303589062694365273422899568998025149162437282946787504989979560840485146728939773930129170543406325876151780259867050243813146058149088981369598561518230 33296932428473487745125653993431865678294565771027470547016729760922998399423193799646110406528940301062084385888299568391011885311448921233425039090758791 29935605751814478098038187949117739774022074983222764257159482210816095837187616607138979308181194217790864349534233152441526053961195096348699907974745917

Finally, we can reassemble all 9 possible mm and decipher our message. 

function long_to_bytes(Val)
  Val == 0 && return ""
  return long_to_bytes(Val ÷ 256) * Char(Val % 256)
end
for Mp in PossibleMp
  for Mq in PossibleMq
    M = (Mp*q*invmod(q, p) + Mq*p*invmod(p, q)) % N
    Str = long_to_bytes(M)
    occursin("ASIS", Str) && println(match(r"ASIS{.*}",Str).match)
  end
end
0.8s
Julia
Julia 1.2
Runtimes (1)