This paGE implements a congruentual public key. In this case Alice will have a private key (\(f,g\)) and a public key (\(h,q\)) and where Bob can cipher a message for her. In this case we will specify the number of bits in \(q\):
Congruential Public Key in Python |
Theory
Alice picks \(f\) and \(g\) and a large prime number \(q\). Then calculates [1]:
\(h=f^{-1}g \pmod q\)
Alice's public key is (\(h,q\)). Bob takes a message (\(m\)) and picks a random number (\(r\)) and ciphers with:
\(e=rh+m \pmod q \)
Alice decrypts with:
\(a=fe \)
\(b=f^{-1}a \pmod g\)
and where \(b\) is the deciphered message.
This works because the value of \(a\) is:
\(a=fe \pmod q = f (rh+m) \pmod q = frh + fm \pmod q = frf^{-1}g+fm \pmod q\)
Now if \(q\) is large, and larger than the value of \(rg+fm\), the value of \(a\) will be:
\(a=rg+fm\)
Now \(b\) is the deciphered message:
\(b=f^{-1}a \pmod g = f^{-1}(rg+fm) \pmod g = f^{-1}rg+f^{-1}fm \pmod g\)
Now the \(f^{-1}rg \pmod g\) part will be zero as we have a multiple of \(g\), and when we apply the \(\pmod g\) operation. So we get:
\(b=f^{-1}fm \pmod g = m \pmod g\)
And if \(g\) is larger than \(m\) we just get the message back.
Coding
The coding is here:
# https://asecuritysite.com/encryption/cong from Crypto.Util.number import * from Crypto import Random import random import Crypto import libnum import sys import math def gcd(a, b): while b: a, b = b, a%b return a m=10 bits=512 if (len(sys.argv)>1): m=(sys.argv[1]) if (len(sys.argv)>2): bits=int(sys.argv[2]) msg="Hello" m= bytes_to_long(msg.encode('utf-8')) q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) bits=bits/4 f=random.randint(1,2**bits) g=random.randint(1,2**bits) while gcd(f, g)>1: g=random.randint(1,2**bits) h=(libnum.invmod(f, q)*g) % q print ("Number of bits in q=%d" % bits) print ("====Private key====\nf=%d" % f) print ("q=%d" % q) print ("\n====Public key====\ng=%d" % g) print ("\nh=%d" % h) print ("\nq=%d" % q) r=random.randint(1,2**64) e=(r*h+m) % q a =(f*e) %q b = (libnum.invmod(f, g)*a) % g print ("\n==Cipher Message===\ne=%d" % e) print ("\n==Dciphered Message===\nmsg=%s" %long_to_bytes(b) )
A sample run:
Number of bits in q=256 ====Private key==== f=14933140596168028708 g=41622122196139493 ====Public key==== h=2855581343810459807212370129565851042120423245653568778866960782627011673790 q=66538782611038628525023778722231841326633644311486527304878827629184162910129 ==Cipher Message=== e=24414432513280572708970988208656059373182332275924909112924745012789026088027 ==Dciphered Message=== msg=Hello
Reference
[1] Hoffstein, J., Pipher, J., Silverman, J. H., & Silverman, J. H. (2008). An introduction to mathematical cryptography (Vol. 1). New York: springer