Congruential public key

Congruential Public Key

My favouriate book at that current time is an easy choice [1]:

I would say I have learnt more from that book than virtually any other, and I often force myself to learn new methods. So let’s pick Section 6.1 on pages 349 and 350, and which implements a congruential public key. It is a great simple example which leads to the coverage of lattices, and then links to the NTRU public key system (and which is being proposed as a post-quantum cryptography method for encryption and signing). You can purchase the Kindle version of the book on Amazon here.

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. Initially, Alice picks f and g and a large prime number q. Then calculates [1]:

h=f^{−1}g (mod q)

=== Important diversion

Note: f^{-1} is the inverse of f mod q, and where f^{-1) times f (mod q) is 1.

Let’s taken an example. If f is 5 and we have a prime of 11. Then f^{-1) (mod 11) is 9 [here], as 9 times 5 is 45 and 45 (mod 11) is 1.

Alice’s public key is (h,q). Bob takes a message (m) and picks a random number (r) and ciphers with:

e=rh+m (mod q)

Alice decrypts with:

a=fe

b=f^{−1}a (mod g)

and where b is the deciphered message. This works because the value of a is:

a=fe(mod q)=f(rh+m)(mod q)=frh+fm(mod q)=frf^{−1}g+fm(mod 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 (mod g)=f^{−1}(rg+fm)(mod g) =f^{−1}rg+f^{−1}fm(mod g)

Now the f^{−1}rg(mod g) part will be zero as we have a multiple of g, and when we apply the (mod g) operation. So we get:

b=f^{−1}fm (mod g)=m (mod g)

And if g is larger than m we just get the message back.

Coding

The coding is [here]:

A sample run [here]:

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