UTCTF

cuman main crypto ez

Name	Category
DCΔ	Cryptography
RSA	Cryptography
Autokey Cipher	Cryptography

1

# DCΔ

Due to a national shortage of primes, the US Department of Agriculture is rationing all citizens to a limit of one generated prime number per CTF challenge.

By Sasha (@kyrili on discord)

we were given a large n and a large c with the e of 65537

seems like the p and q are equal so knowing that this rsa is super easy

the only thing that changed is the way the find φ(n)

φ(n) = (p - 1) * q

from Crypto.Util.number import *
n = 399956368360808862373914258335185223080849636197711424060797090309268643429064461492550414549161330948819635837600839124910339139212025975705016633767495247163243281423582407941339197895052969960664399531226116807938480610953640675838340969642399505783577667601230289640157854573282615113017817753471366212008719316238931155299741896658264134636523008018510523774126757209492757800553768281613227711738371473830681563493341816035127889532515105148615575695347672918819305383651095344758737833444302556494599778991752161562622963652164008980839152347260377969421014616624263631920322958235478733540894255954351848359580013695597870908080170511403061620632540407634608773118202473287854599776791229532885611074739079107324575619148211269673210431496846247978541032947073060592123529635361112170678347924377962162254827262375685704046691718585952854410058401794022674628779309507437739620598639589987596443373586284136126401843497367142210715014480599609277532331148988390798073713743339823218981940779096432112651466716648010370850152213399051968069102663753404120592506704133217642671853086570223710424683386625314802805217882906873879240914022607713870946351691046929143491841506422542038315876506588525639983398522454145866029283449
e = 65537
c = 22644125297186385803212285721101686380290089858624593588464228942417644877688212364383835956263619653769244324906844180248816686517049952319431524113838480708352331162026595736354019259708442449783760846242702532176456117138374450898213788623580234048867117546091028843127595147910526821835855070663317466469650577618010308109119812464711010326075908158768138773973732088207030977470605554056485614676156104134673446546446752627654287202815354367643042773923258958887865030737447323798382020847653880886311162447594373201951226217556835030816588457674298560260109378271244834215832992407457137601161490484862135147963942227371690835380497920998286827898323068399708168699403459009009580152834747843780155917438758224782364193716322974594031272100820264364860227674838730962348140555980411714722361909800417953974064469599278274083750031569853934963716467881656073359393449142980936480726005445774158733389270553554093627622406166942859792490275434896108377393648278975530519769034633686070931694499857110956537102727286491854314244036392929790997824274724196292688659782806587688964714529943288954314300861531138101192901942534064757877725334672680909389193357725470116673323012331269218651347104807494994267835408427908717684178629

p = 19998909179272975096669389773315684909164840476930738123591959958398932097041125093572976768403454709172312115056676217567714135065584289066946488822717110035175886060013869752746528110783649242456127578482532542251448083935376109090114352728675578298146585186423055045769485483629739528100502325926126065585392531444778435555737739407677466146189470978162623830003195010534137805929579970953953819006507688647292456336763899513727791292581312482817948726557865657118159131434894505604528936556072666055920148673374873823318296419969165536109100159362271450418965389139196396590576777869148638544055146306458627451893
q = 19998909179272975096669389773315684909164840476930738123591959958398932097041125093572976768403454709172312115056676217567714135065584289066946488822717110035175886060013869752746528110783649242456127578482532542251448083935376109090114352728675578298146585186423055045769485483629739528100502325926126065585392531444778435555737739407677466146189470978162623830003195010534137805929579970953953819006507688647292456336763899513727791292581312482817948726557865657118159131434894505604528936556072666055920148673374873823318296419969165536109100159362271450418965389139196396590576777869148638544055146306458627451893
phi = (p - 1) * p
d = pow(e, -1, phi)
flag = pow(c, d, n)
print(long_to_bytes(flag))

2

RSA

Idk why people make e so large for rsa... it's so much easier to just use 3. Why use big number when small number do trick?

by jocelyn (@jocelyn3270 on discord)

well thats cool the e is only 3 we can just do a low exponent attack

from Crypto.Util.number import *
import gmpy2

n = 21507386633439519550169998646896627263990342978145866337442653437291500212804540039826669967421406761783804525632864075787433199834243745244830254423626433057121784913173342863755047712719972310827106310978325541157116399004997956022957497614561358547338887866829687642469922480325337783646738698964794799137629074290136943475809453339879850896418933264952741717996251598299033247598332283374311388548417533241578128405412876297518744631221434811566527970724653020096586968674253730535704100196440896139791213814925799933321426996992353761056678153980682453131865332141631387947508055668987573690117314953760510812159
e = 3
c = 6723702102195566573155033480869753489283107574855029844328060266358539778148984297827300182772738267875181687326892460074882512254133616280539109646843128644207390959955541800567609034853
a, b = gmpy2.iroot(c, e)
print(long_to_bytes(a))

3

Autokey Cipher

I know people say you can do a frequency analysis on autokey ciphers over long text, but the flag is short so it'll be fine.

lpqwma{rws_ywpqaauad_rrqfcfkq_wuey_ifwo_xlkvxawjh_pkbgrzf}

by jocelyn (@jocelyn3270 on discord)

knowing its a vigenere we can use dcode to find a part of the key

when brute forcing we found this part so we can just continue