# Super Baby RSA

## June 13 2017

# # # #

Time for RSA!

e = 65537

n = 134023913680045880492110426626164090971954352532495944119602241841766743315344885078078359876157853261789964632342961459801834169156073972150056251259429043527344585589350222304649100454018523375146422111308080990153227407607374257909945989989405880451908900962388521742688809203045971595430040363546058882461

c = 28029822339281125656746130462465126562337695724847502110361462137424051877785282190017747622367185811734822848358173889752744532793526865170001730008026265012114272142868291439355242497819138690415609825725896275747305098862360965342890612304634184172461662826694263502110523984165435588581876100119126419239

p = 10982621221489294931830537773519582919197608543135586716536756890800033254598710943732068869355188441831549541090720220093538940987353399632224377192068317

Flag Format: /flag{.+}/

## Solution

RSA is a cryptosystem which allows for secure data transmission. RSA mangles the `plain text` in a form that makes it `undecipherable` to people without the key, while making it much easier for people with a key to open it and get back the message.

The mathematics is out of the scope of this article, I would encourage a serious reading on your own to figure it out.

The steps to generate a RSA key is as follows.

• Generate two large prime numbers `p`, and `q`.
• `n` = `p` * `q`.
• `e` is a number co-prime to `lcm(p -1, q - 1)` and 1 < `e` < `n`
• `d` = `1 / e mod (p - 1)(q - 1)`

The `1 / e` in this case, should not be confused with division. It is the `inverse_modulo` operation, I.E. `d` is the number, which when multiplied with `e` has the following relation.

``````ed = 1 mod (p - 1)(q - 1)
``````

This notation will also be confusing for a newbie to modular arithmatic. What this means is that

``````(e * d) mod (p - 1)(q - 1) = 1
``````

The public key consists of `n` and `e`. The secret key consists of the rest. Namely, `d`, `p`, `q`.

The security of RSA relies on the one-way trap function of multiplication. Which means that for a function `f`

``````f((x, y)) = x * y | x, y ∈ Z
``````

It is easy enough to go from `(x, y)` to `x * y` (multiplication). But is is far more difficult to go from `x * y` to `(x, y)` (factorization).

The encryption for an message, converted to an integer form, `m` is given as…

``````c = RSA_e_n(m) = m ^ e mod n
``````

`c` is the cipher text. `RSA_e_n` is a notation used to denote that the RSA parameters of `e`, and `n` are constant and a feature of RSA instead of being a part of the arguments to a RSA function.

To get back the `m` from the `c` we require the presence of `d`, which is a good hint as to why it is a part of the `private` key in the first place.

``````m' = inverse_RSA_e_n_d(c) = c ^ d mod n
``````

It is also now interesting to note why `p` and `q` are part of the `private` key. That comes because if you have either of `p` or `q`, generating a `d` for the RSA key is trivial. Because you can easily find the other factor, and quickly generate the `d` via doing a modular_inverse operation of e on base of (p - 1) * (q - 1).

Once `d` is obtained, decryption can be done since you now have the key.

Since this is the introductory RSA problem, I am kind enough to give the `p` directly, which means that this RSA is totally broken.

I also give the following number to integer conversion scheme.

``````A -> 0x41 = 64
AA -> 0x4141 = 16705
AAAAAA -> 0x4141414141 = 280267669825
``````

Which basically says that the number is converted to a hexadecimal representation, and then the hexadecimal is intepreted as an ASCII string.

So now, it's time for some `sage`. Sage Math is a number crunching library with a ton of useful functions built-in.

There are many alternatives to give, but it is a personal preference of quite a few people to use sage, and it is not without reason.

``````e = 65537
n = 134023913680045880492110426626164090971954352532495944119602241841766743315344885078078359876157853261789964632342961459801834169156073972150056251259429043527344585589350222304649100454018523375146422111308080990153227407607374257909945989989405880451908900962388521742688809203045971595430040363546058882461
c = 28029822339281125656746130462465126562337695724847502110361462137424051877785282190017747622367185811734822848358173889752744532793526865170001730008026265012114272142868291439355242497819138690415609825725896275747305098862360965342890612304634184172461662826694263502110523984165435588581876100119126419239
p = 10982621221489294931830537773519582919197608543135586716536756890800033254598710943732068869355188441831549541090720220093538940987353399632224377192068317

q = n / p

d = inverse_mod(e, (p - 1) * (q - 1))

m = pow(c, d, n)

print(m)
``````

This prints out `240545625414703578862070172273428889513126431163886829837844391499244541180606084628879027055096318636117555581`.

Converting this to integer is done by.

``````print(bytes.fromhex(hex(240545625414703578862070172273428889513126431163886829837844391499244541180606084628879027055096318636117555581)[2:]))
``````

Which prints out `b'flag{breaking_rsa_is_easy_if_you_know_the_key}'`. Which is the flag.

## Flag

flag{breaking_rsa_is_easy_if_you_know_the_key}

# Foren-Steg

# # # #

Find the flag, flag finder.

• Flag Format: /flag{.+}/

Provided foren-steg.docx

## Solution

The file provided to us appears to be a docx file. Let us see what happens when we try to open it.

There appears to be nothing in the file but gibberish...

...

# Breaking Random Number Generators with Chosen Seed

# # # #

Find the flag.

Source is as follows

``````#!/usr/bin/env python3

import random
import time
import string
import signal

# use secure seed
random.seed(int(time.time()))

with open('flag.txt') as f: