TheSchmidt-Samoa cryptosystem is an asymmetriccryptographic technique, whose security, likeRabin depends on the difficulty of integerfactorization. Unlike Rabin this algorithm does not produce an ambiguity in the decryption at a cost of encryption speed.

• Choose two large distinct primesp andq and compute${\displaystyle N=p^{2}q}$
• Compute${\displaystyle d=N^{-1}\mathrm{mod}\text{lcm}(p-1,q-1)}$

NowN is the public key andd is the private key.

To encrypt a messagem we compute the ciphertext as${\displaystyle c=m^N\mathrm{mod}N.}$

To decrypt a ciphertextc we compute the plaintext as${\displaystyle m=c^d\mathrm{mod}pq,}$ which like for Rabin andRSA can be computed with theChinese remainder theorem.

Example:

• ${\displaystyle p=7,q=11,N=p^{2}q=539,d=N^{-1}\mathrm{mod}\text{lcm}(p-1,q-1)=29}$
• ${\displaystyle m=32,c=m^N\mathrm{mod}N=373}$

Now to verify:

• ${\displaystyle m=c^d\mathrm{mod}pq={373}^{29}\mathrm{mod}pq={373}^{29}\mathrm{mod}77=32}$

The algorithm, like Rabin, is based on the difficulty of factoring the modulusN, which is a distinct advantage over RSA.That is, it can be shown that if there exists an algorithm that can decrypt arbitrary messages, then this algorithm can be used to factorN.

The algorithm processes decryption as fast as Rabin and RSA, however it has much slower encryption since the sender must compute a full exponentiation.

Since encryption uses a fixed known exponent anaddition chain may be used to optimize the encryption process. The cost of producing an optimal addition chain can be amortized over the life of the public key, that is, it need only be computed once and cached.

• A New Rabin-type Trapdoor Permutation Equivalent to Factoring and Its Applications

• Public-key encryption schemes

• Articles with short description
• Short description matches Wikidata