---
# System prepended metadata

title: PUBLIC-KEY CRYPTOGRAPHY
tags: [CRYPTOHACK]

---

# OVERVIEW
![Screenshot From 2025-03-28 16-29-33](https://hackmd.io/_uploads/ryolPm4Tkg.png)

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
![Screenshot From 2025-03-28 16-46-01](https://hackmd.io/_uploads/SkSOuXNaye.png)

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

## Public Keys
![Screenshot From 2025-03-28 16-51-37](https://hackmd.io/_uploads/SkajFmV6Jx.png)

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
![Screenshot From 2025-03-28 16-57-23](https://hackmd.io/_uploads/HkiWjm461e.png)
### 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`.
![Screenshot From 2025-03-28 17-00-23](https://hackmd.io/_uploads/S1vAjQE6yx.png)

### 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
![Screenshot From 2025-03-28 17-09-29](https://hackmd.io/_uploads/S1hCTXV61x.png)
### solution
```
#!/usr/bin/env python3
d = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932

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

## RSA Signatures
![Screenshot From 2025-03-28 17-16-00](https://hackmd.io/_uploads/ByBwJVEp1x.png)

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
![Screenshot From 2025-03-28 17-21-34](https://hackmd.io/_uploads/Sk1he44a1x.png)

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
![Screenshot From 2025-03-28 17-24-42](https://hackmd.io/_uploads/SkAR-4ET1g.png)

## Monoprime
![Screenshot From 2025-03-28 17-28-49](https://hackmd.io/_uploads/SyBwzVVT1g.png)

also we have been given the file output.txt.
![Screenshot From 2025-03-28 17-30-09](https://hackmd.io/_uploads/SkEpGN4ayx.png)

### 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.
![Screenshot From 2025-03-28 17-34-50](https://hackmd.io/_uploads/ryxkENVT1x.png)


## Manyprime
![Screenshot From 2025-03-28 17-38-17](https://hackmd.io/_uploads/SJo9E4Ep1g.png)

![Screenshot From 2025-03-28 17-39-44](https://hackmd.io/_uploads/r1PgB4VT1e.png)

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).

![Screenshot From 2025-03-28 17-43-23](https://hackmd.io/_uploads/BJfyU44TJx.png)

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.
![Screenshot From 2025-03-28 17-46-07](https://hackmd.io/_uploads/S1wd84NTyl.png)

## Salty
![Screenshot From 2025-03-28 17-47-18](https://hackmd.io/_uploads/ByW1PNE61x.png)

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

![Screenshot From 2025-03-28 17-49-59](https://hackmd.io/_uploads/ryo8wENpyg.png)
![Screenshot From 2025-03-28 17-49-46](https://hackmd.io/_uploads/HJiUvENakg.png)

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)
```
![Screenshot From 2025-03-28 18-03-18](https://hackmd.io/_uploads/BysFqVNp1g.png)

## Modulus Inutilis
![Screenshot From 2025-03-28 18-05-31](https://hackmd.io/_uploads/Skq-oENTyg.png)

Also with this challenge were given two files, modulus_utilis.py and output.txt.
![Screenshot From 2025-03-28 18-07-02](https://hackmd.io/_uploads/By-Ko4Eake.png)
![Screenshot From 2025-03-28 18-06-51](https://hackmd.io/_uploads/SkWYoEN61l.png)

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))
```
![Screenshot From 2025-03-28 18-12-18](https://hackmd.io/_uploads/rkCn3VVpyx.png)


## Working with Fields
![Screenshot From 2025-03-28 18-13-41](https://hackmd.io/_uploads/H14-aVVp1g.png)

### 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
![Screenshot From 2025-03-28 18-18-06](https://hackmd.io/_uploads/H1EWC4NaJe.png)

### 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
![Screenshot From 2025-03-28 18-23-55](https://hackmd.io/_uploads/HJnH1SVpye.png)

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.

![Screenshot From 2025-03-28 18-35-53](https://hackmd.io/_uploads/B1oMfrV61e.png)

### 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)
'''
```
![Screenshot From 2025-03-28 18-39-41](https://hackmd.io/_uploads/S1Ib7SN6kl.png)


## Deriving Symmetric Keys
![Screenshot From 2025-03-28 18-42-15](https://hackmd.io/_uploads/S1q9mBVTyl.png)

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.
![Screenshot From 2025-03-28 18-51-08](https://hackmd.io/_uploads/rJvhBBVTkg.png)


## 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
![Screenshot From 2025-03-28 19-04-36](https://hackmd.io/_uploads/BkP0drN6Jx.png)

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.
![Screenshot From 2025-03-28 19-14-00](https://hackmd.io/_uploads/rJ3Zsr46yl.png)


## 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.
![Screenshot From 2025-03-28 19-21-54](https://hackmd.io/_uploads/r1tFarE61l.png)

```
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
```
![Screenshot From 2025-03-28 19-27-52](https://hackmd.io/_uploads/H1TBCr4T1g.png)

### 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))
```
![Screenshot From 2025-03-28 19-33-26](https://hackmd.io/_uploads/Syt9JU4Tyl.png)


And finally we get our course done.
![Screenshot From 2025-03-28 19-33-57](https://hackmd.io/_uploads/rJOTJ8N6Je.png)
