RSA 4.0

4 minutes to read

We are given the source code in SageMath to encrypt the flag:

import os

from Crypto.Util.number import bytes_to_long, getStrongPrime

m = bytes_to_long(os.getenvb(b"FLAG", b"FAKEFLAG{THIS_IS_FAKE}"))  
e = 0x10001
p = getStrongPrime(1024, e=e)
q = getStrongPrime(1024, e=e)
n = p * q
assert m < n
Q = QuaternionAlgebra(Zmod(n), -1, -1)
i, j, k = Q.gens()
enc = (
    1 * m
    + (3 * m + 1 * p + 337 * q) * i
    + (3 * m + 13 * p + 37 * q) * j
    + (7 * m + 133 * p + 7 * q) * k
) ** e
print(f"{n = }")
print(f"{e = }")
print(f"{enc = }")

And we have the output:

n = 24872021325220256807454685550051664385270234794214413640899222873349265041897698942179745264628886444843936788046461273130347947293134447971213366009115689414264642605438643804813680767747014691971929645215382160557083245742340043385689944268138610186373780437485231877752933652320663858810427971106170059463601595006391073927194512124601928964813763052148657220845548046841237699017168286609835799813635564372682635612722890934578765797156432068449168053296617922489740666171866398517122799604532749283529271598232365042243492016089416298371516093933466381558297769513544950617454777689674801163035308121219081809467
e = 65537
enc = 3859728242860779998500245827824643011031182038976286035325209177561306523157077514772157957170475592309362631020979427907103610597898945426993614901767468098095010971836640454364234772978503167875298045774311291740824611786880849602974611016313651468361669338020331880259928969457255469579663017102640555015734482731890405522757985802082583300838209107911617815694578975817745782743203495107318667111104882994250616348383832987201616468973995462070255337923156614148218730987307161335625736122244817469974403678460213399052200814122255105544573927370423504309249212003649608881714115802854352284801298522985364992841 + 6689400988469336941290409439097720802889756496874465514203924923612416113717282667321908985103298019191113140239387801253466762593814350435047233088038044902433467651291903183405705080977679431528198024945921265445106468212962845547091599919008352051426009980329461007763212773358809391005850095961625042930422795445326743156495371981183105369799111219324695409896763869363969605501957524747716457126557615625815503861788352889135785579006785498195231741997934782780728866125488514068411960643904511224086647859058006472875473225695641287267610159704735294148907843394274092665622496223560673920367014991704447470344*i + 1425535224682533054692632153056888664907065024789232886308473909082337416786879221014972907213731240332278899126018247174859147121923692024420221262194523422785798197856518206508716047860471557004098274123870337912664160290690918788335238938208868363602574049572982498078216870780634694750710402353203621500287688744360281985793220035763469368517282385600578060642616443360598043313771383051760844966304306373372936321033698037647769588864584716070117876256372995523669859957654373351077969273910814003682705611267982200795979916283790161349821926490496096284763527696746485527643315156665082531990553153495043841613*j + 16939641902797542358954398454693773109828645853205801192220966778707379690160425812357360275630857752612391129705744211238057564114356027205464621658979245715243171261351328848491885377078864601014889472906967998503454246639030025900184373900964200415367983329654223213873342814827852864400395905048614694659842857369371845184915252563533413447471945691935551119149323541065035997716667873333295568018189682043599379592763126488255877418142891649422421776838694214872296853180292491137387225104189612300121323951103544193685306688963647668884425837634374966829437978854408218992213680164673972942664618735198830200420*k

Source code analysis

The challenge uses an RSA encryption with quaternions modulo $n = p \cdot q$, where $n$ is the public modulus and $p, q$ are the private prime numbers from a typical RSA setup. As usual, we have $e = 65537$.

Let $m$ be the flag as an integer number, the quaternion that is encrypted is:

$$ z = m + (3m + p + 337q) \,\mathrm{i} + (3m + 13p + 37q) \,\mathrm{j} + (7m + 133p + 7q) \,\mathrm{k} $$

So, $\mathtt{enc} = z^e \mod{n}$.

Solution

After looking for ways to work with quaternions, I found a way to express an $n$-th power of a quaternion here. Let $Q = a + b \,\mathrm{i} + c \,\mathrm{j} + d \,\mathrm{k}$, for $Q^n$ we need to compute:

$$ S = -(b^2 + c^2 + d^2) $$

$$ X = \sum_{i = 0}^{\lfloor\frac{n - 1}{2}\rfloor} {n \choose n - 2i - 1} \cdot a^{n - 2i - 1} S^i $$

Then,

$$ \begin{cases} a_n = \displaystyle\sum_{i = 0}^{\lfloor\frac{n}{2}\rfloor} {n \choose n - 2i} \cdot a^{n - 2i} S^i \\ b_n = b X \\ c_n = c X \\ d_n = d X \end{cases} $$

And $Q^n = a_n + b_n \,\mathrm{i} + c_n \,\mathrm{j} + d_n \,\mathrm{k}$.

Quaternion operations

From the three $(\mathrm{i}, \mathrm{j}, \mathrm{k})$ components, we can find this:

$$ \begin{cases} b_n = b X \\ c_n = c X \\ d_n = d X \end{cases} \iff \begin{cases} b_n = (3m + p + 337q) X \\ c_n = (3m + 13p + 37q) X \\ d_n = (7m + 133p + 7q) X \end{cases} $$

Let’s eliminate $m$:

$$ \begin{cases} b_n = (3m + p + 337q) X \\ c_n = (3m + 13p + 37q) X \\ d_n = (7m + 133p + 7q) X \end{cases} \iff \begin{cases} 7b_n = (21m + 7p + 2359q) X \\ 7c_n = (21m + 91p + 259q) X \\ 3d_n = (21m + 399p + 21q) X \end{cases} $$

$$ \iff \begin{cases} 7c_n - 7b_n = (84p - 2100q) X \\ 3d_n - 7b_n = (392p - 2338q) X \end{cases} $$

Now, let’s eliminate $p$:

$$ \begin{cases} 7c_n - 7b_n = (84p - 2100q) X \\ 3d_n - 7b_n = (392p - 2338q) X \end{cases} \iff \begin{cases} 98c_n - 98b_n = (1176p - 29400q) X \\ 9d_n - 21b_n = (1176p - 7014q) X \end{cases} $$

$$ \iff \begin{cases} 9d_n + 77b_n - 98c_n = 22386q X \end{cases} $$

So, we get that

$$ q X = 22386^{-1} (9d_n + 77b_n - 98c_n) $$

With this result, we can get $q$ using the GCD with $n$:

$ python3 -q
>>> from math import gcd
>>> n = 24872021325220256807454685550051664385270234794214413640899222873349265041897698942179745264628886444843936788046461273130347947293134447971213366009115689414264642605438643804813680767747014691971929645215382160557083245742340043385689944268138610186373780437485231877752933652320663858810427971106170059463601595006391073927194512124601928964813763052148657220845548046841237699017168286609835799813635564372682635612722890934578765797156432068449168053296617922489740666171866398517122799604532749283529271598232365042243492016089416298371516093933466381558297769513544950617454777689674801163035308121219081809467
>>> a_n = 3859728242860779998500245827824643011031182038976286035325209177561306523157077514772157957170475592309362631020979427907103610597898945426993614901767468098095010971836640454364234772978503167875298045774311291740824611786880849602974611016313651468361669338020331880259928969457255469579663017102640555015734482731890405522757985802082583300838209107911617815694578975817745782743203495107318667111104882994250616348383832987201616468973995462070255337923156614148218730987307161335625736122244817469974403678460213399052200814122255105544573927370423504309249212003649608881714115802854352284801298522985364992841
>>> b_n = 6689400988469336941290409439097720802889756496874465514203924923612416113717282667321908985103298019191113140239387801253466762593814350435047233088038044902433467651291903183405705080977679431528198024945921265445106468212962845547091599919008352051426009980329461007763212773358809391005850095961625042930422795445326743156495371981183105369799111219324695409896763869363969605501957524747716457126557615625815503861788352889135785579006785498195231741997934782780728866125488514068411960643904511224086647859058006472875473225695641287267610159704735294148907843394274092665622496223560673920367014991704447470344
>>> c_n = 1425535224682533054692632153056888664907065024789232886308473909082337416786879221014972907213731240332278899126018247174859147121923692024420221262194523422785798197856518206508716047860471557004098274123870337912664160290690918788335238938208868363602574049572982498078216870780634694750710402353203621500287688744360281985793220035763469368517282385600578060642616443360598043313771383051760844966304306373372936321033698037647769588864584716070117876256372995523669859957654373351077969273910814003682705611267982200795979916283790161349821926490496096284763527696746485527643315156665082531990553153495043841613
>>> d_n = 16939641902797542358954398454693773109828645853205801192220966778707379690160425812357360275630857752612391129705744211238057564114356027205464621658979245715243171261351328848491885377078864601014889472906967998503454246639030025900184373900964200415367983329654223213873342814827852864400395905048614694659842857369371845184915252563533413447471945691935551119149323541065035997716667873333295568018189682043599379592763126488255877418142891649422421776838694214872296853180292491137387225104189612300121323951103544193685306688963647668884425837634374966829437978854408218992213680164673972942664618735198830200420  
>>> qX = pow(22386, -1, n) * (9 * d_n + 77 * b_n - 98 * c_n)
>>> q = gcd(n, qX)
>>> q
175803127724826213628253015866242180098615919773503938749518747101563429362503044434349263291624881773473394213047291140818142426601927392424693525893553913022578356625822237407780255755263642470678864638102273800804291156488217599390375904077613536831346388188680603737357334850800743672847839169281380228203
>>> p = n // q
>>> p
141476557596579833574668265391714090690337192180322027886044593295709932858584782075511294793548739215434755212948359663229724283952681236596748859748966677701274874954135379817920423421375005329923490408880041127221023498920731140628880767831913618754023389828289551122285903550392137095478916519269190379889

Decryption

Once we have this, we would need to compute $d$ (the inverse of $e$ modulo the order of $n$ in the quaternion group). However, we can get the flag taking into account that the flag is embedded in the quaternion coordinates.

First, let’s find $X$:

$$ \begin{cases} b_n = (3m + p + 337q) X \\ c_n = (3m + 13p + 37q) X \\ \end{cases} \iff \begin{cases} c_n - b_n = (12p - 300q) X \\ \end{cases} $$

And so,

$$ X = (12p - 300q)^{-1} (c_n - b_n) $$

Once we have $X$, we can get the value of either $b$, $c$ or $d$ and find the flag:

$$ b = b_n \cdot X^{-1} \qquad m = \frac{b - p - 337q}{3} $$

Flag

And this is the flag:

>>> X = pow(12 * p - 300 * q, -1, n) * (c_n - b_n) % n
>>> b = b_n * pow(X, -1, n) % n
>>> m = (b - p - 337 * q) // 3
>>> bytes.fromhex(hex(m)[2:])
b'SECCON{pr0m153_m3!d0_n07_3ncryp7_p_0r_q_3v3n_w17h_r54_4.0}'