1 of 24

Cryptography

Mod 26

Cryptography can be easy, do you know what ROT13 is? cvpbPGS{arkg_gvzr_V'yy_gel_2_ebhaqf_bs_ebg13_uJdSftmh}

We are told that the flag is encrypted with ROT13, which is a simple substitution cipher that replaces every character with the character that is 13 spaces along the alphabet. For example, the character C would be replaced by a P:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

You can see that C is the 3rd index, and P is in fact the 16th. But what if we want to encrypt the letter Y, at index 25? Well, what we do here is we loop back to the beginning; if we do this, the character 13 positions after it is in fact L!

Mathematically, we can see that the index that would be position 26 is actually looping back to position 0, so we add on the 13 and take the remainder modulo 26. We can do this easily in Python, ignoring non-letter characters:

Mind Your Ps and Qs

In RSA, a small e value can be problematic, but what about N? Can you decrypt this? values

This is typical RSA decryption. We are given n, e and c.

If you don't know much about RSA, check out my overview!

All we need are the factors of N. Because it's small, we can try and check if the factors are known using . And they are! So from here it's just standard RSA:

Easy Peasy

A one-time pad is unbreakable, but can you manage to recover the flag? (Wrap with picoCTF{}) nc mercury.picoctf.net 11188 otp.py

We are given a script otp.py and a remote service that serves the script. Let's analyse what it does.

It seems to first start up the process, then it loops an encrypt() function:

print("******************Welcome to our OTP implementation!******************")
c = startup(0)
while c >= 0:
	c = encrypt(c)

startup() has a short process:

So, it will read the flag from the file flag and the key from the file key. It will then grab the first len(flag) bytes of key.

Note this line:

is actually just an XOR operation that returns the result as a hex string. As such, it seems to use the bytes of key as a one-time-pad, XORing it with the flag and returning us the result.

Now let's move on to encrypt():

encrypt() does the same kind of thing, except with our input! The only difference is here:

The end point will be looped around to the start point, so once the first KEY_LEN bytes of the key file are used it will loop back around and start from the beginning. This makes it possible for us to gain the same OTP twice!

I'm going to use pwntools for this process. First we grab the encrypted flag:

Now I will feed a string of length KEY_LEN - enc_flag_len into the encrypt() function. Why? This will make the stop exactly 50000, meaning the next encryption will have a start of 0 again, generating the same OTP as it did for the original flag! Now because XOR is a involution - it undoes itself - we can send back the encrypted flag and it will undo the original XOR, returning us the flag!

Be careful that you decode the hex encoding and send the raw bytes!

The full script is as follows:

The Numbers

The numbers... what do they mean?

We get a bit of an image:

The {} suggest that this is some sort of transposition, where letters are replaced with numbers while other characters are left the same. Since all the numbers are in the range 0-25, it makes logical sense that each number is really the position of the letter in the alphabet. We can make a simple decryption script based off this assumption:

from string import ascii_uppercase

numbers = [16, 9, 3, 15, 3, 20, 6, '{', 20, 8, 5, 14, 21, 13, 2, 5, 18, 19, 13, 1, 19, 15, 14, '}']

flag = ""

for n in numbers:
    if str(n) in "{}":
        flag += n
    else:
        flag += ascii_uppercase[n]

print(flag)

We get QJDPDUG{UIFOVNCFSTNBTPO}. As we assume it starts with PICOCTF, we can see that we are actually one index off - which makes sense, as strings are zero-indexed in Python, so we just need to use n-1 and we get the flag:

from string import ascii_uppercase

numbers = [16, 9, 3, 15, 3, 20, 6, '{', 20, 8, 5, 14, 21, 13, 2, 5, 18, 19, 13, 1, 19, 15, 14, '}']

flag = ""

for n in numbers:
    if str(n) in "{}":
        flag += n
    else:
        flag += ascii_uppercase[n-1]

print(flag)

# PICOCTF{THENUMBERSMASON}

New Caesar

We found a brand new type of encryption, can you break the secret code? (Wrap with picoCTF{}) apbopjbobpnjpjnmnnnmnlnbamnpnononpnaaaamnlnkapndnkncamnpapncnbannaapncndnlnpna new_caesar.py

So we are given a script new_caesar.py, let's analyse it.

So first off we know that the ALPHABET is the first 16 letters in the lowercase alphabet. The key is one character long, and is also in ALPHABET. The flag has b16_encode() run on it, and every letter in the result of that is run under shift(). To reverse, it, we have to first undo shift() and then b16_encode().

shift() is a very simple function, although the arithmetic looks a bit strange. t1 is actually the index of c in ALPHABET, as it grabs the character code and then subtracts off that of a. t2 is the same, but for the key. t2 is then added as a shift to t1 and the index in ALPHABET is returned, so it's essentially a Caesar with a shift dictated by k. We can undo this easily, by subtracting instead of adding:

As for b16encode(), it calculates the 8-bit binary representation of the character code and then splits it into two 4-bit values, which are used as indices in ALPHABET. We can undo this too.

The .zfill(4) ensures that each representation of the two values is 4 bits long, which is very important for parsing it as an 8-bit bniary value at the end!

We then just have to brute force for every possible key in ALPHABET, getting 16 possibilities:

The only one that looks right is et_tu?_23217b54456fb10e908b5e87c6e89156 (given the title), and we submit that as the flag.

Full script:

Mini RSA

What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M ** e) is just barely larger than N. Let's decrypt this: ciphertext

Now we're getting onto proper cryptography. Here we are told that we are using RSA with a small exponent, but $M^e$ is just more than $N$ . This means we can't quite do a cube-root attack, but because it is just more than we can actually keep on adding multiples of onto and taking the cube root until we get the flag. As it is close, it's not infeasible to brute force. I use gmpy2's iroot function to take the cube root.

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot

N = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e = 3

c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808147130204332030239454609548193370732857240300019596815816006860639254992255194738107991811397196500685989396810773222940007523267032630601449381770324467476670441511297695830038371195786166055669921467988355155696963689199852044947912413082022187178952733134865103084455914904057821890898745653261258346107276390058792338949223415878232277034434046142510780902482500716765933896331360282637705554071922268580430157241598567522324772752885039646885713317810775113741411461898837845999905524246804112266440620557624165618470709586812253893125417659761396612984740891016230905299327084673080946823376058367658665796414168107502482827882764000030048859751949099453053128663379477059252309685864790106


for i in range(10_000):
    c_try = c + i * N
    m = int(iroot(c_try, 3)[0])
    flag = long_to_bytes(m)

    if b'pico' in flag:
        print(flag)

# picoCTF{e_sh0u1d_b3_lArg3r_7adb35b1}

Dachshund Attacks

What if d is too small? Connect with nc mercury.picoctf.net 37455.

We are told $d$ is too small, so this is a classic Wiener's Attack. I discuss the technique here, so I won't go over it again. Connecting to the server gives us $e$ , $N$ and $c$ . I will use SageMath for the continued fractions.

from Crypto.Util.number import long_to_bytes

e = 112754541700690073210034568883976704637179938391109984739882317717493134117274992183187134977340726366735137168283197063242918320349494617964667665047419548553575295453656621241958205285249437600208333153358419149045651177119281187188167703425363227405679672963841306943107073166807574585389125832534066751809
N = 144390361348920501869993938709991886178924525779849244222262670433367312227444944591566139662690206095975554337178767396284003325304590032011497856478923049097805457881081418119675617493053963010551906982495811656212858357088185653656378487033852680537367010991060358788282243207315359582442103359642135446811
c = 121200875764971898969856362104661551030573743599078234011937926996191831804013529938239036069865696197047682885988162602437942341629152031466396781294970679065309433084336383355723998945746263068555929945549034859795066917254742307603845777657499038889879448604171444521283481396818702315095487896851743793699


def get_convergences(N, e):
    frac = continued_fraction(e / N)
    convergences = list()

    for i in range(frac.length()):
        convergences.append((frac.numerator(i), frac.denominator(i)))

    return convergences


def factorises(N, e, numerator, denominator):
    if numerator == 0:
        return None

    if denominator % 2 == 0:  # d must be odd
        return None

    phi = (e * denominator - 1) / numerator

    if int(phi) % 2 != 0:  # phi must be an even whole number
        return None

    x = var('x')
    assume(x, 'integer')
    solutions = solve([x ** 2 - ((N - phi) + 1) * x + N], x)

    if len(solutions) == 2:
        return solutions

    return None


for numerator, denominator in get_convergences(N, e):
    factors = factorises(N, e, numerator, denominator)

    if factors:
        p, q = factors

        if p * q == N:
            phi = (p - 1) * (q - 1)
            d = inverse_mod(e, phi)
            m = pow(c, d, N)
            print(long_to_bytes(m))
            break

# picoCTF{proving_wiener_3878674}

No Padding, No Problem

Oracles can be your best friend, they will decrypt anything, except the flag's ciphertext. How will you break it? Connect with nc mercury.picoctf.net 10333

Upon connecting, we get the values of $N$ and $e$ as well as the encrypted ciphertext $c$ that represents the flag. We then have a decryption oracle, which can decrypt anything except for the flag.

Note that the ciphertext is decrypted as follows:

m \equiv c^d \mod N

If we ask to decrypt $-c$ instead, we get

m \equiv (-c)^d \equiv -c^d \mod N

Note the last congruence is because $d$ is odd, so $(-1)^d = -1$ .

This means that if we pass in the negative of $c$ , we can get the negative of the decryption!

There are other ways to do it too - you could calculate and multiply by that, which would yield you after decryption, and you'd just need to halve it, .

Easy1

The one time pad can be cryptographically secure, but not when you know the key. Can you solve this? We've given you the encrypted flag, key, and a table to help UFJKXQZQUNB with the key of SOLVECRYPT

The table is simple - the you grab the plaintext character and the corresponding character from the key and cross-reference them to find the ciphertext character. To reverse it, you find the key character and go along the row (or column) until you find the ciphertext character, then you go perpendicular to it to find the corresponding plaintext character. This nets you CRYPTOISFUN, so the flag is picoCTF{CRYPTOISFUN}.

This is actually a Vigenère cipher, so you could also use an online tool to do it for you!

13

Cryptography can be easy, do you know what ROT13 is? cvpbPGS{abg_gbb_onq_bs_n_ceboyrz}

The same as Mod 26 - check that writeup!

from string import ascii_lowercase, ascii_uppercase

enc_flag = r"cvpbPGS{abg_gbb_onq_bs_n_ceboyrz}"

flag = ""

for c in enc_flag:
    if c in ascii_lowercase:
        flag += ascii_lowercase[(ascii_lowercase.index(c) + 13) % 26]
    elif c in ascii_uppercase:
        flag += ascii_uppercase[(ascii_uppercase.index(c) + 13) % 26]
    else:
        flag += c

print(flag)

# picoCTF{not_too_bad_of_a_problem}

Caesar

Decrypt this message.

A classic caesar cipher, we can decrypt it using an online tool or python:

from string import ascii_lowercase

ciphertext = 'ynkooejcpdanqxeykjrbdofgkq'

for shift in range(26):
    new_c = ''

    for c in ciphertext:
        new_c += ascii_lowercase[(ascii_lowercase.index(c) + shift) % 26]

    print(new_c)

# picoCTF{crossingtherubiconvfhsjkou}

Pixelated

I have these 2 images, can you make a flag out of them? scrambled1.png scrambled2.png

As the images are the same dimensions, it makes sense to consider what could be done with the RBG values. Immediately, XOR springs to mind, and we make a quick script to XOR the pixel data:

from PIL import Image

img1 = Image.open("scrambled1.png")
img2 = Image.open("scrambled2.png")

pixels1 = img1.load()
pixels2 = img2.load()

result_img = Image.new("RGB", img1.size)
result_pixels = result_img.load()

for x in range(img1.width):
    for y in range(img1.height):
        r1, g1, b1 = pixels1[x, y]
        r2, g2, b2 = pixels2[x, y]

        xor_r = r1 ^ r2
        xor_g = g1 ^ g2
        xor_b = b1 ^ b2

        result_pixels[x, y] = (xor_r, xor_g, xor_b)

result_img.save("output.png")

This came up with an interesting output.png, which definitely had the flag in it, but was quite hard to read:

After some trial and error and printing of the values, you notice that pretty much everywhere is pure white. To up the contrast a little, we make all the white into black:

if xor_r == xor_g == xor_b == 255:
    xor_r = xor_g = xor_b = 0

And this was enough to spy the flag:

picoCTF{d562333d}

Basic-Mod1

Take each number mod 37 and map it to the following character set: 0-25 is the alphabet (uppercase), 26-35 are the decimal digits, and 36 is an underscore. Wrap your decrypted message in picoCTF.

Just follow the instructions, really.

from string import ascii_uppercase, digits

numbers = [
    165, 248, 94, 346, 299, 73, 198, 221, 313, 137, 205, 87, 336, 110, 186, 69, 223, 213, 216, 216, 177, 138
]

alphabet = ascii_uppercase + digits + '_'

flag = ''

for n in numbers:
    flag += alphabet[n % 37]

print(flag)

# picoCTF{R0UND_N_R0UND_B6B25531}

Basic-Mod2

Again, simply do what it tells you. For information on the inverse modulo a prime, check out my notes here!

from string import ascii_lowercase, digits
from Crypto.Util.number import inverse

numbers = [
    268, 413, 438, 313, 426, 337, 272, 188, 392, 338, 77, 332, 139, 113, 92, 239, 247, 120, 419, 72, 295, 190, 131
]

alphabet = ' ' + ascii_lowercase + digits + '_'     # space at front because letters start at index 1!
flag = ''

for n in numbers:
    idx = inverse(n % 41, 41)
    flag += alphabet[idx]

print(flag)

# picoCTF{1nv3r53ly_h4rd_8a05d939}

Credstuff

We found a leak of a blackmarket website's login credentials. Can you find the password of the user cultiris and successfully decrypt it? Download the leak here.

Opening up usernames.txt and passwords.txt in Pycharm, we see cultiris is on line 378 of usernames.txt so we go to line 378 of passwords.txt and find an encrypted password:

cvpbPGS{P7e1S_54I35_71Z3}

The {} are in place, implying that it's some sort of transposition cipher for the letters. We've done it numerous times, but we try a caesar cipher decode:

from string import ascii_lowercase, ascii_uppercase

enc_flag = 'cvpbPGS{P7e1S_54I35_71Z3}'

for shift in range(26):
    flag = ''

    for c in enc_flag:
        if c in ascii_lowercase:
            flag += ascii_lowercase[(ascii_lowercase.index(c) + shift) % 26]
        elif c in ascii_uppercase:
            flag += ascii_uppercase[(ascii_uppercase.index(c) + shift) % 26]
        else:
            flag += c

    print(flag)

# picoCTF{C7r1F_54V35_71M3}

In fact the shift is 13, so it's just a ROT13.

morse-code

Pretty explicitly morse code, we go to an online decoder and have it spit out the flag:

picoCTF{WH47_H47H_90D_W20U9H7}

Alternatively we could use something like Audacity to view the waveforms themselves, but nah.

rail-fence

A type of transposition cipher is the rail fence cipher, which is described here. Here is one such cipher encrypted using the rail fence with 4 rails. Can you decrypt it?

So, you can use an online tool like here, or you can actually follow the wikipedia page it gives you, or you can play around until it works:

T     a     -     _     7     N     6     D     4     9
 h   l g   : W   3 D   _ H   3 C   3 1   N _   _ A   9 7
  e f   - s   H R   0 5   3 F   3 8   N 4   3 D   7 B
   -     i     3     3     _     _     _     N     6

The flag is: WH3R3_D035_7H3_F3NC3_8361N_4ND_3ND_4A76B997

So the flag is picoCTF{WH3R3_D035_7H3_F3NC3_8361N_4ND_3ND_4A76B997}

Substitution0

A message has come in but it seems to be all scrambled. Luckily it seems to have the key at the beginning. Can you crack this substitution cipher?

So, we are told that the key is at the beginning! Let's see what we have:

ZGSOCXPQUYHMILERVTBWNAFJDK 

Qctcnrel Mcptzlo ztebc, fuwq z ptzac zlo bwzwcmd zut, zlo gtenpqw ic wqc gccwmc
xtei z pmzbb szbc ul fqusq uw fzb clsmebco. Uw fzb z gcznwuxnm bsztzgzcnb, zlo, zw
wqzw wuic, nlhlefl we lzwntzmubwb—ex sentbc z ptczw rtukc ul z bsuclwuxus reulw
ex aucf. Wqctc fctc wfe tenlo gmzsh brewb lczt elc cjwtciuwd ex wqc gzsh, zlo z
melp elc lczt wqc ewqct. Wqc bszmcb fctc cjsccoulpmd qzto zlo pmebbd, fuwq zmm wqc
zrrcztzlsc ex gntlubqco pemo. Wqc fcupqw ex wqc ulbcsw fzb actd tcizthzgmc, zlo,
wzhulp zmm wqulpb ulwe selbuoctzwuel, U senmo qztomd gmzic Ynruwct xet qub eruluel
tcbrcswulp uw.

Wqc xmzp ub: ruseSWX{5NG5717N710L_3A0MN710L_357GX9XX}

So, the first line appears to be the "key". Well, if we write the alphabet under it:

ZGSOCXPQUYHMILERVTBWNAFJDK
ABCDEFGHIJKLMNOPQRSTUVWXYZ

There is a perfect correspondence! So, any instance of the character in the top list is meant to be substituted using the bottom list. We can easily make a python program to do it for us:

We get a text from The Gold-Bug, by Edgar Allen Poe and the flag too:

Substitution1

A second message has come in the mail, and it seems almost identical to the first one. Maybe the same thing will work again.

Similar to Substitution0, this is a substitution cipher but without the key. We could use online tools, but let's think about how we could maybe determine it ourselves.

Firstly, I'm going to put the entire text to lowercase. I will set the alphabet to full underscores, and only fill it in once I know the transposition; the underscores will denote transpositions I do not know. In the transposition step, if the character is not know it prints it lowercase, while the ones I do know are printed uppercase.

alphabet = '---------------------------'
#           ABCDEFGHIJKLMNOPQRSTUVWXYZ

text = '''
SYTe (eakdy tkd sjbyndr yar thjm) jdr j yobr kt skxbnyrd ersndzyo skxbryzyzkc. Skcyreyjcye jdr bdrercyrq gzya j ery kt sajhhrcmre gazsa yrey yarzd sdrjyzwzyo, yrsaczsjh (jcq mkkmhzcm) evzhhe, jcq bdklhrx-ekhwzcm jlzhzyo. Sajhhrcmre nenjhho skwrd j cnxlrd kt sjyrmkdzre, jcq garc ekhwrq, rjsa ozrhqe j eydzcm (sjhhrq j thjm) gazsa ze enlxzyyrq yk jc kchzcr eskdzcm erdwzsr. SYTe jdr j mdrjy gjo yk hrjdc j gzqr jddjo kt skxbnyrd ersndzyo evzhhe zc j ejtr, hrmjh rcwzdkcxrcy, jcq jdr akeyrq jcq bhjorq lo xjco ersndzyo mdknbe jdkncq yar gkdhq tkd tnc jcq bdjsyzsr. Tkd yaze bdklhrx, yar thjm ze: bzskSYT{TD3UN3CSO_4774SV5_4D3_S001_7JJ384LS}
'''.lower()

# we start lowercase, and make capital letters for ones we know

dec = ''

for c in text:
    if c in alphabet:
        dec += ascii_uppercase[alphabet.index(c)]    # if we know the transposition, good
    else:
        dec += c

print(dec)

Initially this prints the text out as is. However, let's see the flag at the end:

We can determine the characters for p, i, c, o, t and f because we know the flag format!

Now the plaintext when printed out looks more interesting, as it includes this:

Let's look at the rest of the text and see what we can determine.

The first word is CTFe, implying that is should say CTFS, as not much else can follow CTF.

Then, later, it says

which looks like it should say CTFS ARE A ..., and we can put those letters in too. By this point we have

And leter on the word PRACTICE is already decrypted. Now you continue the process, seeing words such as SERwICE. We eventually get

With the key

Note some letters are missing. The script currently looks like this:

Now we're gonna reuse the one from to transpose it for us (with a couple of minor modifications):

Substitution2

It seems that another encrypted message has been intercepted. The encryptor seems to have learned their lesson though and now there isn't any punctuation! Can you still crack the cipher?

This time around, we don't even have spaces or full stops!

isnfnnpctitnznfmxhisnfwnxxntimjxctsnascdstushhxuhgqbinftnubfciruhgqnicichktckuxbackdurjnfqmifchimkabturjnfusmxxnkdnisntnuhgqnicichktehubtqfcgmfcxrhktrtingtmagckctifmichkebkamgnkimxtwscusmfnznfrbtnebxmkagmfonimjxntocxxtshwnznfwnjnxcnznisnqfhqnfqbfqhtnhemscdstushhxuhgqbinftnubfciruhgqnicichkctkhihkxrihinmuszmxbmjxntocxxtjbimxthihdnitibankitckinfntinackmkanpucinamjhbiuhgqbinftucnkunanenktcznuhgqnicichktmfnheinkxmjhfchbtmeemcftmkauhgnahwkihfbkkckdusnuoxctitmkanpnubickduhkecdtufcqitheenktnhkisnhisnfsmkactsnmzcxrehubtnahknpqxhfmichkmkacgqfhzctmichkmkaheinksmtnxngnkitheqxmrwnjnxcnznmuhgqnicichkihbusckdhkisnheenktcznnxngnkitheuhgqbinftnubfcirctisnfnehfnmjniinfznscuxnehfinusnzmkdnxctgihtibankitckmgnfcumkscdstushhxtebfisnfwnjnxcnznismimkbkanftimkackdheheenktczninuskcvbntctnttnkicmxehfghbkickdmkneenuicznanenktnmkaismiisnihhxtmkauhkecdbfmichkehubtnkuhbkinfnackanenktcznuhgqnicichktahntkhixnmatibankitihokhwisncfnkngrmtneenuicznxrmtinmusckdisngihmuicznxrisckoxconmkmiimuonfqcuhuiectmkheenktcznxrhfcnkinascdstushhxuhgqbinftnubfciruhgqnicichkismitnnotihdnknfminckinfntickuhgqbinftucnkunmghkdscdstushhxnftinmusckdisngnkhbdsmjhbiuhgqbinftnubfcirihqcvbnisncfubfchtcirghiczmickdisngihnpqxhfnhkisncfhwkmkankmjxckdisngihjniinfanenkaisncfgmusckntisnexmdctqcuhUIE{K6F4G_4K41R515_15_73A10B5_702E03EU}

We can use a similar approach to last time, but this time we may have to use frequency analysis (as suggested by the last flag!) and even bi- and trigram analysis. This means finding common letters, or common groupings of 2/3 letters, and comparing it to what would typically occur in a regular english text.

However, first off, there is very clearly a flag at the end:

qcuhUIE{K6F4G_4K41R515_15_73A10B5_702E03EU}

And we can use the same initial approach as last time and update the alphabet accordingly.

I can then see the following string:

so there is a word P*TITIO*. According to a , that's either petition or petitios. But ahead of it, there's even more:

This looks like COMPETITION! Let's throw that in.

After spotting lots more words like cybersecurity etc, I get the alphabet:

And we use the decrypt again:

As we can see from the flag (and also the hint), analysis was the way to go.

Transposition-Trial

Our data got corrupted on the way here. Luckily, nothing got replaced, but every block of 3 got scrambled around!

So we are given the data

heTfl g as iicpCTo{7F4NRP051N5_16_35P3X51N3_V6E5926A}4

And also told that every block of 3 is scrambled the same way. Looking at the first block of 3, is should clearly say The, so the order of reading it should be 3rd letter -> 1st letter -> 2nd letter. We make a quick python script to split it into triplets and rearrange:

message = 'heTfl g as iicpCTo{7F4NRP051N5_16_35P3X51N3_V6E5926A}4'

trigrams = [message[x:x+3] for x in range(0, len(message), 3)]

dec = ''

for t in trigrams:
    dec += t[2] + t[0] + t[1]

print(dec)

# The flag is picoCTF{7R4N5P051N6_15_3XP3N51V3_56E6924A}

Vigenere

Can you decrypt this message?

So the hint is that the message is encrypted with a Vigenere cipher using the key CYLAB. Sure we could use an online tool, but how about in python?

The way a vigenere cipher works is that the letters in the key are converted into integers based into their position in the alphabet, with 0 being a and 25 being z. Those values are then used as shift values for a per-letter caesar cipher - so in the case of CYLAB, the first value is 3 and the second is 24. Given the encrypted flag:

rgnoDVD{O0NU_WQ3_G1G3O3T3_A1AH3S_2951c89f}

We then know that r is the plaintext letter shifted over by 3 and g is the plaintext letter shifted over by 24 (and looped around, in the same way a caesar cipher is). To this end, we can make a quick script:

We get the output

Which isn't quite the flag. Evidently, it's working.

After a lot of trial and error, it turns out that the problem is that we are looping throuhg them at the same pace, but in reality the key isn't even being incremented on the non-letter characters (for example the L in the key aligns with { in the message, nothing is done because it's not a character, but the loop still goes on to the next key character for the next decryption). In essence, we have to just stop the key from looping on those characters:

HideToSee

How about some hide and seek heh? Look at this image here.

Not the most enjoyable challenge. Gives us an image called atbash.jpg, but no ciphertext yet. We actually have to use steganography techniques to extract the ciphertext from being embedded in the image, using steghide:

$ steghide extract -sf atbash.jpg

The passphrase is empty. The encrypted.txt file that is created has the following:

krxlXGU{zgyzhs_xizxp_8z0uvwwx}

Based off the filename, we can assume it's an atbash cipher, which is essentially a transposition cipher where alphabet is flipped (so A goes to Z, B goes to Y, etc).

No Padding, No Problem

Oracles can be your best friend, they will decrypt anything, except the flag's ciphertext. How will you break it? Connect with nc mercury.picoctf.net 10333

Upon connecting, we get the values of $N$ and $e$ as well as the encrypted ciphertext $c$ that represents the flag. We then have a decryption oracle, which can decrypt anything except for the flag.

Note that the ciphertext is decrypted as follows:

m \equiv c^d \mod N

If we ask to decrypt $-c$ instead, we get

m \equiv (-c)^d \equiv -c^d \mod N

Note the last congruence is because $d$ is odd, so $(-1)^d = -1$ .

This means that if we pass in the negative of $c$ , we can get the negative of the decryption!

N = 64225632402784743608151428388331019007158039700441403609620876723228303996217136829769322251101831115510439457268097599588978823846061420515078072743333076016253031234729517071419809456539618743788851473244412318432363995783182914809195026673348987512316519371501063936603604905070428868194818209957885002651
R = IntegerModRing(N) 
c = R(23961525860638788006091919862301366730415613260613078904461027043559403510831473561860834624403033454974614369313881141911510211211764847671996788759608002057996932820692709010900418723347410147858586280735791816478632919784849715797867137711835451159040091442311708166252069010315360215005284477472628144578)
print(-c)

# send it back, get result
negative_m = R(64225632402784743608151428388331019007158039700441403609620876723228303996217136829769322251101831115510439457268097599588978823846061420515078072743333076016253031234729517071419809456249343713593001433770955700064908110713217165957916949916605267065613204854099704669280835867601177422810391570120236404254)
long_to_bytes(-m)

# picoCTF{m4yb3_Th0se_m3s54g3s_4r3_difurrent_1772735}

There are other ways to do it too - you could calculate and multiply by that, which would yield you after decryption, and you'd just need to halve it, .

Mini RSA

What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M ** e) is just barely larger than N. Let's decrypt this: ciphertext

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot

N = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e = 3

c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808147130204332030239454609548193370732857240300019596815816006860639254992255194738107991811397196500685989396810773222940007523267032630601449381770324467476670441511297695830038371195786166055669921467988355155696963689199852044947912413082022187178952733134865103084455914904057821890898745653261258346107276390058792338949223415878232277034434046142510780902482500716765933896331360282637705554071922268580430157241598567522324772752885039646885713317810775113741411461898837845999905524246804112266440620557624165618470709586812253893125417659761396612984740891016230905299327084673080946823376058367658665796414168107502482827882764000030048859751949099453053128663379477059252309685864790106


for i in range(10_000):
    c_try = c + i * N
    m = int(iroot(c_try, 3)[0])
    flag = long_to_bytes(m)

    if b'pico' in flag:
        print(flag)

# picoCTF{e_sh0u1d_b3_lArg3r_7adb35b1}

Dachshund Attacks

What if d is too small? Connect with nc mercury.picoctf.net 37455.

from Crypto.Util.number import long_to_bytes

e = 112754541700690073210034568883976704637179938391109984739882317717493134117274992183187134977340726366735137168283197063242918320349494617964667665047419548553575295453656621241958205285249437600208333153358419149045651177119281187188167703425363227405679672963841306943107073166807574585389125832534066751809
N = 144390361348920501869993938709991886178924525779849244222262670433367312227444944591566139662690206095975554337178767396284003325304590032011497856478923049097805457881081418119675617493053963010551906982495811656212858357088185653656378487033852680537367010991060358788282243207315359582442103359642135446811
c = 121200875764971898969856362104661551030573743599078234011937926996191831804013529938239036069865696197047682885988162602437942341629152031466396781294970679065309433084336383355723998945746263068555929945549034859795066917254742307603845777657499038889879448604171444521283481396818702315095487896851743793699


def get_convergences(N, e):
    frac = continued_fraction(e / N)
    convergences = list()

    for i in range(frac.length()):
        convergences.append((frac.numerator(i), frac.denominator(i)))

    return convergences


def factorises(N, e, numerator, denominator):
    if numerator == 0:
        return None

    if denominator % 2 == 0:  # d must be odd
        return None

    phi = (e * denominator - 1) / numerator

    if int(phi) % 2 != 0:  # phi must be an even whole number
        return None

    x = var('x')
    assume(x, 'integer')
    solutions = solve([x ** 2 - ((N - phi) + 1) * x + N], x)

    if len(solutions) == 2:
        return solutions

    return None


for numerator, denominator in get_convergences(N, e):
    factors = factorises(N, e, numerator, denominator)

    if factors:
        p, q = factors

        if p * q == N:
            phi = (p - 1) * (q - 1)
            d = inverse_mod(e, phi)
            m = pow(c, d, N)
            print(long_to_bytes(m))
            break

# picoCTF{proving_wiener_3878674}