OVERVIEW

This course was very helpful to people who are willing to learn RSA in deep and how to play around with basic concepts to intermediate concepts and also how to solve RSA problems with programming language skills. My main aim was to understand RSA and use my python skills to solve the problems.

The course consist of 18 lessons, while i was solving this course 80% i used python and 20% i used pen and piece of paper, but will try to solve it here with python from lesson 1-18

Modular Exponentiation

solution

#!/bin/env python3
b = 101 # base
e = 17 # exponent
N = 22663 # modulus
print("The flag is: ", pow(b,e,N))

Public Keys

Were required to compute for the ciphertext.

solution

#!/bin/env python3
e = 65537
p = 17
q = 23
m = 12 # message

print("The ciphertext is: ", pow(m,e,p*q))

Euler's Totient

solution

#!/bin/env python3
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
print("Euler's totient value is: ", (p-1)*(q-1))

Private Keys

The challenge needs us to compute for the value of the private key d.

solution

#!/bin/env python3
p = 857504083339712752489993810777
q = 1029224947942998075080348647219 
e = 65537

print("The value of d is: ", pow(e,-1,(p-1)*(q-1)))

RSA Decryption

solution

#!/usr/bin/env python3
d = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932

plain = pow(c,d,e)
print("The plaintext: " ,plain)

RSA Signatures

Now here we have been given an additional private.key file which consist of N and d

solution

#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Hash import SHA256

## step to get the signature
'''
1.Hash the message: Compute the SHA256 hash of the message.
2.Convert the hash to an integer: Use the bytes_to_long() function to convert the hash into a number that can be used with RSA math.
3.Sign the hash: Encrypt the hash with your private key using the RSA signing formula: S=H(m)dmod  NS=H(m)dmodN.
'''
#N = input("Enter the value of N: ")
#d = input("Enter the value of d: ")
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
secret_message = b'crypto{Immut4ble_m3ssag1ng}'

# hash the secret message with sha256
hash_object = SHA256.new(secret_message)
hash_bytes = hash_object.digest()

# convert the hash to an integer
hash_int = bytes_to_long(hash_bytes)

# sign the signature with private key
signature = pow(hash_int,d,N)

print("The signature: ", signature)

Factoring

Factorise the 150-bit number 510143758735509025530880200653196460532653147 into its two constituent primes. Give the smaller one as your answer.The simplest way to factorize such type of number we can do this with online(factordb.com) method.

solution

Monoprime

also we have been given the file output.txt.

solution

This challenge demotrate the use of one prime number, on the next challenge we will see how we can solve manyprimes challenge.

#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
from Crypto.PublicKey import RSA

## Given
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591

## calculating phi
phi = n -1 
d = inverse(e,phi)
print(long_to_bytes(pow(ct,d,n)))

And on trying to run the script you get the flag.

Manyprime

In order to solve this challenge, we need first to find these prime numbers from N, we can use online too or simple python script. Am going to use online tool(factordb.com).

Now my next step here was to create a array of these factors and use for loop.

solution

#!/bin/env python3
from Crypto.Util.number import bytes_to_long, long_to_bytes

factors = [
    9282105380008121879, 9303850685953812323, 9389357739583927789, 10336650220878499841,
    10638241655447339831, 11282698189561966721, 11328768673634243077, 11403460639036243901,
    11473665579512371723, 11492065299277279799, 11530534813954192171, 11665347949879312361,
    12132158321859677597, 12834461276877415051, 12955403765595949597, 12973972336777979701,
    13099895578757581201, 13572286589428162097, 14100640260554622013, 14178869592193599187,
    14278240802299816541, 14523070016044624039, 14963354250199553339, 15364597561881860737,
    15669758663523555763, 15824122791679574573, 15998365463074268941, 16656402470578844539,
    16898740504023346457, 17138336856793050757, 17174065872156629921, 17281246625998849649
]
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
phi = 1
for i in factors:
    phi*=(i-1)

d = pow(e,-1,phi)

decrypt = pow(ct,d,n)
print("decrypt:",decrypt)
print(long_to_bytes(decrypt))

And when we run the script we get our flag.

Salty

also this challenge we can see were given two files, which are salt.py and output.txt

From the code above we can see that ths script starts by importing the libraries, then initialize the value of d and e and then compute for the value of p and q ,phi and d but also good enough we can see how the ciphertext and plaintext is being generated, now from here lets try to implement the script that can solve all this all and give us a flag.

Implementing the solution of this was is very simple since because the value of e=1, we can only convert the ct from long_t0_bytes and we get the flag.

solution

#!/bin/env python3
from Crypto.Util.number import long_to_bytes

ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
decrypted = long_to_bytes(ct)
print(decrypted)

Modulus Inutilis

Also with this challenge were given two files, modulus_utilis.py and output.txt.

Now again we need to understand the script given and what we need to work on so as we can get the flag.

From the script above now we can see we have been given a small exponential again, possible attack here is small exponential attack.

solution

#!/bin/env python3
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
from gmpy2 import iroot
#attack: Small Exponential attack

n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

#print(long_to_bytes(ct))
pt, exact = iroot(ct, 3)
print("Flag:", long_to_bytes(pt))

Working with Fields

solution

#!/bin/env python3
import math

p = int(input("Enter p:"))
g = int(input("Enter g:"))

d = pow(g,-1,p)
print("Value of d:" ,d)

Generators of Groups

solution

def primitive_root_checker(g, p):
    p_minus = p - 1
    factors = [2, 5, 563]  # Prime factors of 28150
    if pow(g, p_minus, p) != 1:
        return False
    for q in factors:
        if pow(g, p_minus // q, p) == 1:
            return False
    return True

p = 28151
g = 2
while not primitive_root_checker(g, p):
    g += 1

print(f"The smallest primitive root of {p} is {g}")

Computing Public Values

Well the description and details are very straight forward we just need to understand about Diffie-Hellman protocol and the paramater and from here we can solve the rest the of the challenges.

Since because we have all the value we can just use pow() to ge the calculate the public value with pow(g,a,p).

solution

#!/bin/env python3
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919 
a = 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815 

result = pow(g,a,p)
print("The output is: ", result)

Computing Public Values

In this challenge we will forcus on solving the shared secret, we all know that the shared secret between bob and alice should be the same.

solution

#!/bin/env python3
g = int(input("Enter g: "))
p = int(input("Enter p: "))
A = int(input("Enter A: "))
b = int(input("Enter b: "))

print("The value of B: " ,pow(g,b,p))
print("The Bob shared secret is: " ,pow(A,b,p))

'''
Alternative calculating shared_secret from alice
we need alice private key(a)
'''

Deriving Symmetric Keys

Well this time were provided with some additional information such as IV and ciphertext but also were beeen given a almost simplified script that we will be using along the way to solve this challenges.

solution

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')


shared_secret = 1547922466740669851136899009270554812141325611574971428561894811681012510829813498961168330963719034921137405736161582760628870855358912091728546731744381382987669929718448423076919613463237884695314172139247244360699127770351428964026451292014069829877638774839374984158095336977179683450837507011404610904412301992397725594661037513152497857482717626617522302677408930050472100106931529654955968569601928777990379536458959945351084885704041496571582522945310187 
iv = '737561146ff8194f45290f5766ed6aba'
ciphertext = '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'

print(decrypt_flag(shared_secret, iv, ciphertext))

And when we run the script we get the flag.

Parameter Injection

You're in a position to not only intercept Alice and Bob's DH key exchange, but also rewrite their messages. Think about how you can play with the DH equation that they calculate, and therefore sidestep the need to crack any discrete logarithm problem.

Use the script from "Deriving Symmetric Keys" to decrypt the flag once you've recovered the shared secret.

Connect at socket.cryptohack.org 13371

solution

First of all before automating everything, we have to understand what we want to automate. Here what i did,we can see what is being sent/received is json format, so I tried to send some bogus json data in the format they want us to send and observe it up to the end, i.e

Something to keep in mind that the encrypted_flag and IV keep changing, so inorder to find a way to decrypt this we need something like pwntools and the schema of decryption script we were given in the previous challenge.

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from pwn import *
import json

def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

p = remote('socket.cryptohack.org', 13371)
p.recvuntil("Send to Bob:")
p.sendline(b'{"p":"0x01","g":"0x02","A":"0x03"}')
p.recvuntil("Intercepted from Bob:")
p.sendline(b'{"B":"0x01"}')
p.recvuntil(b"Intercepted from Alice:")
data = p.readline().strip()
data = json.loads(data)
iv = data["iv"]
ciphertext = data["encrypted_flag"]
shared_secret = 1
print(decrypt_flag(shared_secret, iv, ciphertext))

And we finally get the flag.

Export-grade

What we have done from the previous challenge is what were going to apply but we will just make a simple twist based with the output we get after connecting back.

Alice and Bob are using legacy codebases and need to negotiate parameters they both support. You've man-in-the-middled this negotiation step, and can passively observe thereafter. How are you going to ruin their day this time?

Connect at socket.cryptohack.org 13379

solution

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from pwn import *
import json
from sympy.ntheory.residue_ntheory import *  #help to calculate 'a' from diff Helman alg

def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

# remote connection
r = remote('socket.cryptohack.org', 13379)
r.recvuntil('Send to Bob:')
r.sendline(b'{"supported": ["DH64"]}')
r.recvuntil('Send to Alice:')
r.sendline(b'{"chosen": "DH64"}')
r.recvuntil('Intercepted from Alice:')
data = r.readline().strip()
data = json.loads(data)
p = int(data["p"], 16)
g = int(data["g"], 16)
A = int(data["A"], 16)
r.recvuntil("Intercepted from Bob:")
data = r.readline().strip()
data = json.loads(data)
B = int(data["B"], 16)
r.recvuntil("Intercepted from Alice:")
data = r.readline().strip()
data = json.loads(data)
iv = data["iv"]
ciphertext = data["encrypted_flag"]

# calculating shared secret
'''
From
A = pow(g,a,p) - we have everything except 'a'
B = pow(g,b,p) - we have  no b,

calculating a
a =discrete_log(p,A,g)
b =discrete_log(p,B,g)

Then 
shared_secret(alice) = shared_secret(bob)
shared_secret = pow(B,a,p)
'''
a = discrete_log(p, A, g)
b = discrete_log(p, B, g)
print("The value of a and b", {a,b})
#print(sharedSecretAlice = pow(A,b,p))
#SharedSecretBob = pow(B,a,p)
#print("Alice & Bob shared secret: ", {SharedSecretAlice,SharedSecretBob})
shared_secret = pow(B,a,p)
print("Shared_secret is: ", shared_secret)
print(decrypt_flag(shared_secret, iv, ciphertext))

And finally we get our course done.