David Naccache and Jacques Stern — And The Uncracked Method With Homomorphic Addition

RSA has survived nearly five decades and is still going strong. However, there have been other methods for public key encryption that have not quite scaled the levels of RSA. And, so, in 1997, David Naccache and Jacques Stern produced a knapsack method for public key encryption, and which has still to be broken [1][here]:

Before we cover the Naccache-Stern Knapsack cryptosystem, we will first cover the method created by Ralph Merkle and Marty Hellman [2]:

Knapsack encryption provides a good approach to creating public and private keys, where the private key is easy to use, while the public key is difficult to compute. Within five years of the paper being published, Adi Shamir [3] cracked it, and so RSA was clear to become the de facto method: