Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# Author: Bill Buchanan
# source: https://asecuritysite.com/encryption/pal_ex
from random import randint
import sys
def gcd(a,b):
"""Compute the greatest common divisor of a and b"""
while b > 0:
a, b = b, a % b
return a
def lcm(a, b):
"""Compute the lowest common multiple of a and b"""
return a * b / gcd(a, b)
def extended_euclidean_algorithm(a, b):
"""
Returns a three-tuple (gcd, x, y) such that
a * x + b * y == gcd, where gcd is the greatest
common divisor of a and b.
This function implements the extended Euclidean
algorithm and runs in O(log b) in the worst case.
"""
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = b, a
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
return old_r, old_s, old_t
def inverse_of(n, p):
"""
Returns the multiplicative inverse of
n modulo p.
This function returns an integer m such that
(n * m) % p == 1.
"""
gcd, x, y = extended_euclidean_algorithm(n, p)
assert (n * x + p * y) % p == gcd
if gcd != 1:
# Either n is 0, or p is not a prime number.
raise ValueError(
'{} has no multiplicative inverse '
'modulo {}'.format(n, p))
else:
return x % p
def L(x,n):
return ((x-1)//n)
p=17
q=19
m=10
if (len(sys.argv)>1):
m=int(sys.argv[1])
if (len(sys.argv)>2):
p=int(sys.argv[2])
if (len(sys.argv)>3):
q=int(sys.argv[3])
if (p==q):
print("P and Q cannot be the same")
sys.exit()
n = p*q
gLambda = lcm(p-1,q-1)
gLambda = int(gLambda)
g = randint(20,150)
if (gcd(g,n*n)==1):
print("g is relatively prime to n*n")
else:
print("WARNING: g is NOT relatively prime to n*n. Will not work!!!")
r = randint(20,150)
l = (pow(g, gLambda, n*n)-1)//n
gMu = inverse_of(l, n)
k1 = pow(g, m, n*n)
k2 = pow(r, n, n*n)
cipher = (k1 * k2) % (n*n)
l = (pow(cipher, gLambda, n*n)-1) // n
mess= (l * gMu) % n
print("p=",p,"\tq=",q)
print("g=",g,"\tr=",r)
print("================")
print("Mu:\t\t",gMu,"\tgLambda:\t",gLambda)
print("================")
print("Public key (n,g):\t\t",n,g)
print("Private key (lambda,mu):\t",gLambda,gMu)
print("================")
print("Message:\t",mess)
print("Cipher:\t\t",cipher)
print("Decrypted:\t",mess)
print("================")
print("Now we will add a ciphered value of 2 to the encrypted value")
m1=2
k3 = pow(g, m1, n*n)
cipher2 = (k3 * k2) % (n*n)
ciphertotal = (cipher* cipher2) % (n*n)
l = (pow(ciphertotal, gLambda, n*n)-1) // n
mess2= (l * gMu) % n
print("Result:\t\t",mess2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment