2
$\begingroup$

I've been stuck in this problem for a while, this is a challenge about Symmetric RSA:

We know that

$N = p*q$

$e = p$

$ct = pt^p \bmod N$ (1)

We are given $ct$ (which is the flag encrypted) and 4 more $ct$ where we can freely choose 4 numbers (plaintext) then the server will return new CT respectively using $p$ and $N$ (we don't know $p$, $q$ and $N$). How to find $p$ and $N$? I tried to do research on my own and something seem to be helpful are Little Fermat and DLP

Little Fermat: $a^p \equiv a \bmod p$ ($p$ is prime and $a$ is not divisible by $p$)

DLP: $g^x \equiv h \bmod p$ Then what is $x$?

Please help me I will be very grateful.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ $\text{ct}\equiv\text{pt}^p\bmod n$ is ambiguous. It can be read as $\text{ct}\equiv\text{pt}^p\pmod n$ which means $n$ divides $\text{pt}^p-\text{ct}$ and thus does not uniquely define $\text{ct}$, allowing e.g. $\text{ct}=\text{pt}^p$ or $\text{ct}=\text{pt}^p-42\,n$. Also, why $N$ and $n$? I think it's meant $\text{ct}=\text{pt}^p\bmod N$, where$\bmod$ is an operator meaning remainder of the Euclidean division $\endgroup$
    – fgrieu ♦
    Commented Aug 12 at 9:20
  • 1
    $\begingroup$ Thanks fgrieu for helping me, I edited the question to make it clearer. I do understand the finding q part but we don't have N how can I find its factors? $\endgroup$
    – Ahn
    Commented Aug 12 at 16:40
  • 2
    $\begingroup$ Revised hint: using a single pair $(m,c)$ with $c=m^p\bmod N$ and $1<m<N-1$, and Fermat's little theorem, we get a multiple of $p$. Using two, we get $p$. From there, uh, thinking about it. $\endgroup$
    – fgrieu ♦
    Commented Aug 12 at 22:44

1 Answer 1

Reset to default
1
$\begingroup$

Thanks fgrieu for your help. I found out the answer for this question.

Recover p

First we compute:

$ct1 = 2^p \bmod N$

$ct2 = 3^p \bmod N$

$gcd$ ($2$,$N$) and $gcd$ ($3$,$N$) should be $=$ 1

So that we can apply Fermat's little theorem:

$2^p \equiv 2 (\bmod p)$

$3^p \equiv 3 (\bmod p)$

after rearranging, we got:

$ct1 - 2 \equiv 0 (\bmod p)$

$ct2 - 3 \equiv 0 (\bmod p)$

Since they are divisible by p, then we can find p by using gcd:

$p = gcd(ct1 - 2, ct2 - 3)$

Recover N

We sent -1 to server:

$ct3 = (-1)^p (\bmod N)$

Because $p$ is odd so $(-1)^p = -1$

$ct3 \equiv -1 \equiv N - 1 (\bmod N)$

then $N = ct3 + 1$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ If the server did not accept the input $-1$, we could in principle also get $N$ (or a typically small multiple thereof) as $\gcd(2^p-\text{ct2},3^p-\text{ct3})$. We can then pull the small factors, if any. Or, rarely, we'd need one or two other queries to get the actual $N$. Problem is the numbers involved are huge, so at least the fist step of the GCD needs to be done specially. $\endgroup$
    – fgrieu ♦
    Commented Aug 13 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.