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

### Algorithm

def generate_key(k): |

### Cipher

pubkey = 1043247381320041410146374847683905608886067988802815759655490071506964811427733496668055364700822779908166748193534341903285387332658081562041534228961538451830025041762537639985150344917584064827615356535763872539925989984117068207555498700585376330731428359489791600319636079777025344217248475485835298689437926003958578141784379857951264973109214803916445702964047899447002191548965239884095802091798787988745415178578597206815122915438351636672681355517982410123569961242563194480399347961753678159210217993526738306796503660563163029287419732210247579793266891085178817047536758465239950861266592524206390869822972469137566045176690277813352563392838847417674529251627419479815097868890993153215515488877097760272399483111013602618554846096893805108827211344467797072352072430591318485091677011261912992157762106672216780766138057271434398274272110062768324672899209610001835423246735718435995420720133657793744810610657 |

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

privkey = inverse(pubkey, l) |

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$.

kphi = (priv*pub-1) |

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

try $p$ or $q$ first :

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

cp = enc % p |

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

cq = enc % 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?!!