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
1
2
3
4
5
6
7
8
9
| def generate_key(k):
p, q = getPrime(k), getPrime(k)
pubkey = p**2 * q
l = (p-1)*(q-1) / gcd(p-1, q-1)
privkey = inverse(pubkey, l)
return pubkey, privkey
def encrypt(m, pubkey):
return pow(bytes_to_long(m), pubkey, pubkey)
|
Cipher
1
2
3
| pubkey = 1043247381320041410146374847683905608886067988802815759655490071506964811427733496668055364700822779908166748193534341903285387332658081562041534228961538451830025041762537639985150344917584064827615356535763872539925989984117068207555498700585376330731428359489791600319636079777025344217248475485835298689437926003958578141784379857951264973109214803916445702964047899447002191548965239884095802091798787988745415178578597206815122915438351636672681355517982410123569961242563194480399347961753678159210217993526738306796503660563163029287419732210247579793266891085178817047536758465239950861266592524206390869822972469137566045176690277813352563392838847417674529251627419479815097868890993153215515488877097760272399483111013602618554846096893805108827211344467797072352072430591318485091677011261912992157762106672216780766138057271434398274272110062768324672899209610001835423246735718435995420720133657793744810610657
privkey = 105717877672224295784291675385546750129601472163379527375367128238003471793097341763391999503913659542087520808364287167645349555897774428176288829031477703594776341268160433668976237198330124904372546897953955241778475322074160469767162566234358907740412805211247598698481640207956827199048419949848619731050860757808082106844953602176503247786535423423104239566910713528691298692332149783689032722772009974404716783312200885555343877611094998117307970399241640213553820043460140493803404190774171912962651075100983834071259021038322886114660028788229094872545516054757700068264628024524394995795135464746570071201
enc = 343369686707916921497078851452395954252074753628024855326592148594828266567853497784448902839960599855457261387659174943864861324798607407210198762531665500523668627672623380100283047707927966101715266190355476680204081288124100983003649559499979731342450364456322062273208742008750774795951290651360492364136674198126979777860541228166734597108964573061640243513571440689299166495541329990802602494896619995591485311779060353650700199981044058309406067935205196708178000370643018639282003328307492888263256672104905274453644042024751439967243049147724769464785043328741645419214885736940487139062463786022104540986811119563549305718088453842093257734689508882969016290658885961965896726616361694426487326338043950416067501288065942862535560013037283761552797410980713186506671844418096395304234050342551849999867017770968633512178545044838766793795733222455421862835695299142219006201321417882617773291364153890050471244104
|
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.
1
| 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$.
1
2
3
4
| kphi = (priv*pub-1)
pq = gcd(pow(2,kphi,pub)-1,pub)
p = pubkey // pq
q = pq // p
|
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$
1
2
3
| cp = enc % p
d = invmod(q,p-1)
pow(cp,d,p)
|
Q : $m^{p^2q} \equiv m^{p^2} \ mod \ q$
1
2
3
| cq = enc % q
d = invmod(p,q-1)
pow(cq,d**2,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?!!
