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 diversionNote: 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…
