Maojui

## ASIS 2018 - Uncle-Sam (Crypto, 123)

2018-05-01

### Challenge :

Uncle Sam needs your help! (With a png file)

I think … we familiar with code, not png LoL.
Give it to Online OCR first.

### Solution

We known l is just a least common multiple of $(p-1)(q-1)$ ,

$LCM(p-1)(q-1) = [\phi({p}),\phi({q})] = k \dot (p-1)(q-1) = k\dot\phi({p})\dot\phi({q})$

then privkey is pubkey’s inverse multiplicative modular in l field.

this means

$priv * pub = 1 \ mod\ [\phi({p}),\phi({q})]$

$\rightarrow priv * pub - 1 = n * k(p-1)(q-1)$

By Fermat, we know that :

$$a^{ K(p-1) } \equiv 1{\ mod\ {p} }$$

$$\Rightarrow a^{ K(p-1) } -1 = np$$

If exponent contains $\phi(p)$, then we can get a number which has a factor $p$.

Here, we modulo another number $N$ which $p|N$, so that we can calculate $a^{ K(p-1) }$ in reasonable time and ensure $n$ is still $p|n$.

### Solution

Therefore, If exponent contains $\phi(p)*\phi(q)$, then we can get num have factors $p,q$.

Now, we get

$priv * pub - 1 = n*k(p-1)(q-1)$, this is contain $\phi(p)\phi(q)$

do modulo operation with pubkey($p^2q$), so we can get a number $n$, $pq|n$.

After Getting p & q, is time to make $m^{pubkey} = m^{p^2q} \rightarrow m^1$

try $p$ or $q$ first :

### Q : $m^{p^2q} \equiv m^{p^2} \ mod \ q$

#### flag : ASIS{Y0u_c4N_m4n493_Schmidt_5am0A_CryP7o_SysT3M!!}

If flag is long enough, Maybe use CRT on them, but it’s just solved now.

P.S. I have known after challenges that this is so-called Schmidt-Samoa Cryptosystem … OAO?!!