22-12-07-2022CnHoneKe

The competition was held in August.

The exercises except factor2 are done. And the article is mainly aim to make a record for myself. The Modus is about the multiplicative homomorphic system, which is similar to the Extended Euclidean algorithm.

List

• Modus
• rsa
• factor2
• secret_data

Wish I can solve out above.

Modus

• multiplicative_homomorphic

output.txt

n = 14142010206099386143235977555692857399310494373372334255226213043954222671886219214790080363755519983589419573494262932031062165425660149023699589427423291076757673539031113758789961660789969074666728548356143546954548237178966812807683542026090314756465049840269239582841323515153189937744280883895942616355068450477244038093783025761830910527817275117470273068582606801561816182028771714266926279491448124072638544823523354972471012076902504991756879694948477398253632905720027515230565063830199860044535605314432273647912553716877788661706091962626029470938285869557993283863813783012548154763397158585969860496209
e1 = 8044170206501208651566242545498471362911890649958881015968520025930186294576023443506808099677296038797758573489705294289102108150592764180571398770862282775413964383616485564171756065468610971753771700993772575426420613330938626182989999507422559869431997096499661057456703567386749182728255894961711
c1 = 11517322714245526592044873592382373283428914348422645739336159016405003731268657488015847458779166523731678788259036486197351408324218938844963108776390284845014868126098529982171539875948326597563481747612010865265679909207769244324752454968172401384300433252342047155447253514663020084257315172025978213587941036806257025876560069777775117798912056950800470305039358493009376541529192357082470617915062674822440632959240104574498373020678875137349967659371746447815516349204225897744273956308472359601558104152900628002351072193856499370256139818744736463310402972428459727204523498170929275318085749369313370330104
e2 = 7981110843177277522743262582712207767500318326009118362192817529414323700650435360291001887232564132664914694220334201133850645107707193720930288877874115700468049318771691746592219604611120450612600603061311788240065247605723819417162805390035814213048743243801428908542140081097421519822132590047533
c2 = 12907231513900923422005862146378905589636791955213455533815625546155661275692081099543894853443339737652933422555561840945917851059973294781475696342510739464313686827430856742266071924616860913810640580296234473777303348248031669837803543965896443694327322478656672147536068477193332582821244877632320706358476947499828283809012293724747791713411303065091158644428874828519807586496004634361827049528190857803358038226873772036022804215684911051370929474550764142943510840488678370689581686370179457811111602201500802245275266633124851078915997894235280935026230159846619929979668248511374747926732890795947582868735
e3 = 8321945773137532897701269832287423438330975369722946793416731752574708023263908693097168458920645511451157398450278461406044452962800707032660103849647429968263806321843635237930345258217128805872313308435747131438472827261934005675575066641207582827978944766548998867180054428477087525524476746729443
c3 = 14065425026445215199826296511184881258323064633386950509660192854866326626040354040592178906620984652169865998063876885421774133239148395916412178848784041317916589243316140373118461629430419305769180856968279675982734449182890302977853892881391084830333333875116598959777525928574769839174695101654696531535920235825780434207646161363349309470260223615977113109458426965856166705879375711518022880712089324008258280991081209228374850515248942548172463741894540420262751207821783524890116559086561517224038086473047623408064157594299815732082781632190258405091440187576055868450259807171733509904666142689629066721239

Analyse

When I see the output.txt, the first thing appeared in my mind is the SameModAttack, using the Extended-Extended Euclidean algorithm. :)

Obviously it is wrong, and the correct solution is to use the multiplicative homomorphic properties.

From the output, we can get a condition that gcd(e1, e2, e3) = 1. Using the Extended Euclidean algorithm we can get $gcdext(a, b) \Longrightarrow gcd(a, b) = r * a + s * b$.

By deduction, we will get the relation that:
$$
gcd(e1, e2) \equiv e1 * r1 + e2 * s1
$$

$$
gcd(gcd(e1, e2), e3) \equiv gcd(e1, e2) * r2 + e3 * s2
$$

$$
\Longrightarrow 1 \equiv (e1 * r1 + e2 * s1) * r2 + e3 * s2
$$

Using this important equation, we can deduce the plaintext:
$$
c1^{r1 \cdot r2} * c2^{r2 \cdot s1} * c3^{s3} \mod n
$$

$$
\Longrightarrow m^{e1\cdot r1 \cdot r2 + e2 \cdot r2 \cdot s1 + e3 \cdot s2} \equiv m \mod n
$$

And we can solve out the important m.

exp.py

from gmpy2 import *
from Crypto.Util.number import *
g1, r1, s1 = gcdext(e1, e2)
g2, r2, s2 = gcdext(g1, e3)
print(g2)
# 1
m = powmod(c1, r1*r2, n)*powmod(c2, r2*s1, n)*powmod(c3, s2, n) % n
print(m)
# 158364088221424626103916028957988006099747465255174624548375855659785449250446255975244653061928080738353296765
print(long_to_bytes(m).decode())
# CnHongKe{e4d0e72e-7589-46a5-973a-cb2a561ab9b5}

rsa

• Euler function 2
• fermat factor

task.py

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
import gmpy2

m = bytes_to_long(flag)
p1 = getPrime(256)
p2 = gmpy2.next_prime(p1)
q1 = getPrime(256)
q2 = gmpy2.next_prime(q1)
n = p1 * p2 * q1 * q2
e = 65537
c = pow(m, e, n)
print "n = %s" % str(n)
print "c = %s" % str(c)

# n = 64167976067579049714960625453369319623574147507612434283986049223337768780480307767872484679214997588434480836733456745370562072077109044069294552424055163225824033286416753073591864962033181307822913035174676405849974928866646899569297852568167037383571518655075260561571463850326020102574832776970253538663
# c = 61862798948167945139222097835309318688214053098609025632041946354708220281670731577734398373186075525909035569024535800893559811995294302363408878574730352951360726686941143742759917076156204564133401228995322937563878389120770732315714920284214472911769619065607001763986611359218449802649142381309774537696

Analyse

From the code, we can make a conclusion that the p1 and p2 are primes which are neighbors, and the q1 and q2 are the same.

At this time, we can use fermat factor to solve out the different p1, p2, q1 and q2.

The n is Composite number , so we will use Euler function 2 to solve out $\varphi(n)$.

We use fermat factor to make a possible list and make sure that the n = p1 * p2 * q1 * q2

factor2

secret_data

• change and fix the data
• convert data to zip
• zip to xlsx
• kali-grep to find the flag