PicoCTF-2021 Writeup
  • README
  • Binary Exploitation
    • Binary Gauntlet 0
    • Binary Gauntlet 1
    • Stonks
    • What's your input?
  • Cryptography
    • Compress and Attack
    • Dachshund Attacks
    • Double DES
    • Easy Peasy
    • It is my Birthday 2
    • It's Not My Fault 1
    • Mini RSA
    • New Caesar
    • New Vignere
    • No Padding, No Problem
    • Pixelated
    • Play Nice
    • Scrambled: RSA
  • Forensics
    • Disk, disk, sleuth!
    • Disk, disk, sleuth! II
    • information
    • MacroHard WeakEdge
    • Matryoshka doll
    • Milkslap
    • Surfing the Waves
    • Trivial Flag Transfer Protocol
    • tunn3l v1s10n
    • Very very very Hidden
    • Weird File
    • Wireshark doo dooo do doo...
    • Wireshark twoo twooo two twoo...
  • Reverse Engineering
    • ARMssembly 0
    • ARMssembly 2
    • ARMssembly 3
    • ARMssembly 4
    • gogo
    • Hurry up! Wait!
    • keygenme-py
    • Let's get dynamic
    • Rolling My Own
    • Shop
    • speeds and feeds
    • Transformation
  • Web Exploitation
    • Ancient History
    • Bithug
    • GET aHEAD
    • It is my Birthday
    • More Cookies
    • Most Cookies
    • Scavenger Hunt
    • Some Assembly Required 1
    • Some Assembly Required 2
    • Some Assembly Required 3
    • Some Assembly Required 4
    • Super Serial
    • Web Gauntlet 2
    • Web Gauntlet 3
    • Who are you?
    • X marks the spot
Powered by GitBook
On this page
  • Problem
  • Solution
  • Flag

Was this helpful?

Edit on GitHub
  1. Cryptography

Mini RSA

PreviousIt's Not My Fault 1NextNew Caesar

Last updated 2 years ago

Was this helpful?

Problem

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

Solution

  1. I spent a while (2 hours) searching for resources to solve this. However, is where I found the solution. Other helpful resources include: , , , and

  2. Without padding, encryption of m is m^e mod n: the message m is interpreted as an integer, then raised to exponent e, and the result is reduced modulo n. If e = 3 and m is short, then m^3 could be an integer which is smaller than n, in which case the modulo operation is a no-operation. In that case, you can just compute the cube root of the value you have. However, we cannot simply compute c^(1/3) (where c is the ciphertext) because there is a slight amount of padding to the message to make m^e larger than n, which makes the modulo operation take effect.

  3. With a short m slightly wider than n^(1/e), which is what we have, we are given c = m^e mod n and can find by enumeration k such that k * n + c is an eth power: then m = (k * n + c)^(1/e).

  4. We can use python and write a to search though thousnads of values for k until we find one that contains the start of the flag. When we find the padding amount, we can increase the precision and rerun the calculation to get the entire flag. Keeping the precision high enough just to see the beginning of the flag speeds up the enumeration of k.

Flag

picoCTF{e_sh0u1d_b3_lArg3r_a166c1e3}

ciphertext
this Cryptography StackExchange comment
RSA Padding Schemes - Wikipedia
Cryptography StackExchange 1
Cryptography StackExchange 2
Cryptography StackExchange 3
solution script