Zeromutarts CTF Crypto Challenges

The magic of rsa (100)

You were able to hear some whispering on the last crypto party! *whisper* d is 35181901. Keep it secret or we are doomed!

We were given 2 files for the challenge.

1) rsa.py

#!/usr/bin/env python

import sys

n= 65354147
e = 13

d = ??

f = open( sys.argv[1] , "r" )
for line in f: 
    line = int(line.strip())
    # you'll have to insert the decrypt function for each line(number) here!
    #dec = ...
    print chr(dec)

2) rsa.txt

If you read up about RSA decryption[0] on Wikipedia, it's pretty simple and straightforward to solve this challenge. You need C = ciphertext (we got loads of it there in rsa.txt, just need to use one by one), d = private key exponent (we got that as well), n = modulus for both private and public keys. Thus, M (plaintext) = C^d mod n

Here, I used sagemath[1] cloud application to solve it as follows. You could actually save the following into a python script and run it.

n = 65354147
d = 35181901
ctuple = [32588732,56947340,16730166,16529146,17037091,9958499,18895626,49410873,

58063242,16529146,18895626,30273022,58063242,30273022,60194095,9956852,58063242,4

4337129,16730166,5059543,40999214,39158796,5059543,58063242,54302449,9958499,5806

3242,8646641,16730166,51307370,16730166,57845836,16730166,34996934,32762958]
result = ""

for i in ctuple:
    lol = pow(i, d, n)
    result += chr(lol)
print "Result for http://zeromutarts.de/task/rsa_magic : " + result

rivest-shamir-adleman (250)

This one is important, we have no clue how to decrypt the secret message! Can you help us?

We were given 2 files for this challenge as well.

1) rivest.py

#!/usr/bin/env python

import sys

n= 80646413
e = 5

# You'll have to find the d yourself..
d = unknown

f = open( sys.argv[1] , "r" )
for line in f: 
    line = int(line.strip())
    # you'll have to insert the decrypt function for each line(number) here!
    #dec = ...
    print chr(dec)

# might come handy
def xgcd(a,b):
    """Extended GCD:
    Returns (gcd, x, y) where gcd is the greatest common divisor of a and b
    with the sign of b if b is nonzero, and with the sign of a if b is 0.
    The numbers x,y are such that gcd = ax+by."""
    prevx, x = 1, 0;  prevy, y = 0, 1
    while b:
        q, r = divmod(a,b)
        x, prevx = prevx - q*x, x
        y, prevy = prevy - q*y, y
        a, b = b, r
    return a, prevx, prevy

def modinv(a, m):
    """Modular multiplicative inverse, i.e. a^-1 = 1 (mod m)"""
    a, u, v = xgcd(a, m)
    if a <> 1:
        raise Exception('No inverse: %d (mod %d)' % (a, m))
    return u

2) rivest.txt

This time we seriously need sagemath to solve it. :) Since we don't know the d to decrypt the messages for this challenge, we first need to find the p & q to get d. The most straightforward way to get that is to use Fermat's Factorization method[2].

I used the formula from here: http://facthacks.cr.yp.to/fermat.html to get p & q.

n = 80646413
e = 5
ctuple = [72895864,15633602,38820479,60303684,7458706,60299530,20682371,54642689,

26066811,32615038,35349196,76400140,38820479,56463813,80491201,76400140,35349196,

69567074,26066811,76400140,74270178,76127647,76127647,15633602,76400140,60303684,

38820479,56463813,60303684,76400140,72844764,76127647,69302434,15633602,80491201,

76400140,6809712,26066811,76400140,42498798,60299530,76127647,69302434,80491201,3

3234011]

def fermatfactor(N):
       if N <= 0: return [N]
       if is_even(N): return [2,N/2]
       a = ceil(sqrt(N))
       while not is_square(a^2-N):
         a = a + 1
       b = sqrt(a^2-N)
       return [a - b,a + b]
p, q = fermatfactor(n)

phi=(p-1)*(q-1)
d=pow(e,-1,phi)

result = ""
for i in ctuple:
    lol=pow(i,d,n)
    result+=chr(lol)
print "Result for result http://zeromutarts.de/task/rivest-shamir-adleman : " + result

[0]: https://en.wikipedia.org/wiki/RSA_(algorithm)#Decryption
[1]: https://cloud.sagemath.com
[2]: https://en.wikipedia.org/wiki/Fermat's_factorization_method

:: FLOSS Bytes - MavJS ::

12 November 2013