Crypto Conspiracy | Part 3 | PicoCTF

6 min readSep 12, 2022

Welcome back to the 3rd Part of this ongoing Cryptography series. As mentioned earlier, this series is about solving cryptography challenges and providing write-ups and explanations as we counter new concepts and techniques.

For curious minds, links are attached for further reading and deep scouting into the concepts.

Part 3 will cover further six challenges from PicoCTF, from where we left last time.

6. Mini RSA

Description:

As the name reveals, this is an RSA challenge. The description of the challenge further gave us a hint of the solution. The message(m) is padded and raised to the power of the public exponent(e). The produced number is just barely larger than modulo N.

The challenge contains a ciphertext file attached:

N: 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287  e: 3  ciphertext (c): 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808146919581675891411119628108546342758721287307471723093546788074479139848242227243523617899178070097350912870635303707113283010669418774091018728233471491573736725568575532635111164176010070788796616348740261987121152288917179932230769893513971774137615028741237163693178359120276497700812698199245070488892892209716639870702721110338285426338729911942926177029934906215716407021792856449586278849142522957603215285531263079546937443583905937777298337318454706096366106704204777777913076793265584075700215822263709126228246232640662350759018119501368721990988895700497330256765579153834824063344973587990533626156498797388821484630786016515988383280196865544019939739447062641481267899176504155482

Modulo operation is applied on the raised number with N, producing ciphertext(c). As mentioned above, the number isn’t that large, so we can brute-force the number of cycles(k) and get the original padded message(m).

mᵉ > n m = ᵉ√(k*n + ct)

It is called Direct Root Attack. I have covered detailed explanations and resources of this attack in my last post.

Let’s carve a simple python script to obtain the flag:

Executing the script generates the flag and k value.

As you can see, decoded m contains padded spaces before the flag.

Flag: picoCTF{e_sh0u1d_b3_lArg3r_60ef2420}

7. Dachshund Attacks

Description:

The description reads that the value of d is small and provides a remote netcat server to connect.

Connecting with it stages out e, n and c values, which indicates it is an RSA challenge. The unusual part is the value of e(public exponent) which is very large.

e: 113965669847310828500899853435537445886983372706073821582740688051084844590270657144802211593866034167958454899416336731100816582959179216508158889366467881403093573232820412893929890484121606858090638065014168581359200003029491515859319460603694717588289450599381971738052585390819540519174165042131365401533
n: 132003680749217325264675831117281105874525666627537898834125189765815508087804891675517950739058534804759886578814128106898450995862925449069584216322388240003964796961657830300533744405435697226675534656722606914801264956767259152996066985017938022450355910333175552359165701760451785353064163355112500095881
c: 44749543223058762425469734395376800216388486724804166144918800099402890297286168669084372989795199561374348875497306461363768838480401641692065469119034403679064279508236432654110240860922620611182038801976878736850247293258430369111173858786169423491552197826994459460266609051093131934975124305804834932124

There is a relation between the values of e and d. As the value of e increases, d decreases. (Inversely proportional)

d = e^(−1) modϕ(n)

In an ideal RSA encryption, the private exponent d must be large enough. If not, and with few other factors, the encryption can break using Wiener’s attack

It’s a cryptographic attack against RSA. The attack uses the continued fraction method to expose the private key d when d is small.

I won’t go into deeper details about how the attack works but will provide resources to study it.

A Classic Wikipedia page on the Wiener attack, a great article, a cryptohack blog page describing the Wiener attack and a YouTube video won’t hurt.

There is a python3 implementation of wieners attack on github. Download the script, and import the functionality into your custom script to calculate d.

Make sure the downloaded script is in the same folder as your script.

A custom script may look something like this:

Executimg the script returns the flag.

Flag: picoCTF{proving_wiener_6907362}

8. No Padding, No Problem

Description:

The challenge provides a remote netcat server to connect.

Here is the output:

The output produced again indicates that it is an RSA challenge. The catch here is that the server will decrypt any other ciphertext but the ciphertext of the flag produced.

The above output confirms it.

To solve this, we somehow have to do some computations on the encrypted cyphertext and after decrypting the result via the remote server, figure out the way to retrieve the original m.

This computation can be done using Homomorphic encryption. Homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, results in an identical output to that produced had the operations been performed on the unencrypted data.

Read further here.

This homomorphic property can be used on RSA, where we can multiply the encrypted cypher with another encrypted cypher. It looks something like this:

encrypt(m1) * encrypt(m2) = ((m1**e)*(m2**e)) mod n = (m1*m2)**e mod n = encrypt(m1*m2)

Now we can choose a value like 2 and encrypt it using 2**e mod n. Multiply the result with ct. The returned value can be decrypted by the server. Then dividing the decrypted value with 2 will give us our m1(flag in long).

Let’s first generate our cyphertext from 2.

Lets multiply the cyphertext with the original ct of the flag.

Slap this calculated ct3 into the server to get the decrypted m1m2.

m1m2 = 580550060391700078946913236734911770139931497702556153513487440893406629034802718534645538074938502890769281669222390720762

Lets now divide the m2 which is 2 with the above value to get m1.

Now lets just convert this value into bytes.

Flag: picoCTF{m4yb3_Th0se_m3s54g3s_4r3_difurrent_4005534}

9. Easy1

Description:

The challenge provides an encrypted flag(UFJKXQZQUNB), a key(SOLVECRYPTO) and a file named table. Viewing the table contents and the key hints that it is a Vigenère cypher.

Vigenère is again a substitution cypher where each letter of the plain string shifts +n times. The plain string and the key are mapped together as the key repeats itself until it matches the length of the plain string. n is the position of the key’s letter in ALPHABET, which shifts its adjacent letter in plain text.

You can read further about it here.

To decrypt the encrypted flag, shift the string with -n, where n is described above.

We can create a simple python script to automate our task.

Flag: picoCTF{CRYPTOISFUN}

10. 13

Description:

It is a simple rot13 challenge. It is a substitution cipher. Read more about it in my first post.

Ciphertext:

cvpbPGS{abg_gbb_onq_bs_n_ceboyrz}

Cyberchef to the rescue!

Flag: picoCTF{not_too_bad_of_a_problem}

11 — caesar

Description:

As the name of the challenge indicates that it is an easy Caeser cypher challenge. It is a simple and easy-to-use encryption technique. It is a kind of substitution cypher, where every letter of the plain string is replaced by a letter of some fixed number of positions down the alphabet.

Read further about it here.

The challenge provides a ciphertext file which contains the encrypted flag.

picoCTF{dspttjohuifsvcjdpoabrkttds}

There are about 26 possible shifts in caesar cypher. No hints given so we can brute force the flag with every possible shift, and try to recognize the flag.

A script can be written to automate the task: