RSA - Decryption - Given p, q and e - Calculate m(message) from c(cipher text) - Algorithm: Extended Euclidean - sage @ zhsh 2023

rsa_egcd.sage

# -*- coding: utf-8 -*-
# RSA - Decryption - Given p, q and e - Calculate m(message) from c(cipher text) - Algorithm: Extended Euclidean - sage @ zhsh 2023
# @author  zhsh - https://zhsh9.info/ - https://zhsh9.info/RedTeam101/
# @license Creative Commons Attribution-ShareAlike 4.0 International License - http://creativecommons.org/licenses/by-sa/4.0/

# p, q, e, c -> Integer
p = 7493025776465062819629921475535241674460826792785520881387158343265274170009282504884941039852933109163193651830303308312565580445669284847225535166520307
q = 7020854527787566735458858381555452648322845008266612906844847937070333480373963284146649074252278753696897245898433245929775591091774274652021374143174079
e = 30802007917952508422792869021689193927485016332713622527025219105154254472344627284947779726280995431947454292782426313255523137610532323813714483639434257536830062768286377920010841850346837238015571464755074669373110411870331706974573498912126641409821855678581804467608824177508976254759319210955977053997
c = 44641914821074071930297814589851746700593470770417111804648920018396305246956127337150936081144106405284134845851392541080862652386840869768622438038690803472550278042463029816028777378141217023336710545449512973950591755053735796799773369044083673911035030605581144977552865771395578778515514288930832915182

n = p * q
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)  # Extended Euclidean

m = pow(c, d, n)
int_m = int(m)  # Convert m to a standard Python int before converting to hexadecimal
print("int_m", int_m)

# Convert m to hexadecimal, then to bytes, and finally decode it to a string
hex_m = hex(m_int)[2:]  # Convert to hexadecimal and remove '0x' prefix
hex_m = hex_m[:-1]      # Delete last letter L for long int
print("hex_m", hex_m)

# Convert hexadecimal string to byte array
bytes_m = ''.join(chr(int(hex_m[i:i+2], 16)) for i in range(0, len(hex_m), 2))

str_m = bytes_m.decode('utf-8')  # Decode bytes to string
print("m", str_m)