The Schmidt-Samoa public key encryption method uses an modulus of \(n\) and which is \(p^2q\) and where \(p\) and \(q\) are large prime numbers [paper]:
Schmdit-Samoa public key |
Method
The method is similar to RSA, but uses the modulus for the encryption key value (N). First we pick two random prime numbers (p and q) and then calculate the modulus (N) of:
\(N=p^2 q\)
Next we determine the private key (\(d\)) with:
\(d= e^{-1} \pmod {lcm(p-1,q-1)} \)
Our public key is \(N\) and the private key is \((p,q)\). Next we cipher with:
\(c=m^N \pmod N\)
And decrypt with:
\(m=c^d \pmod N\)
Coding
The coding is:
import sys import libnum import Crypto from Crypto.Util.number import * from Crypto import Random import random import math def gcd(a,b): """Compute the greatest common divisor of a and b""" while b > 0: a, b = b, a % b return a def lcm(a, b): """Compute the lowest common multiple of a and b""" return a * b // gcd(a, b) bits=60 msg="hello" if (len(sys.argv)>1): msg=str(sys.argv[1]) if (len(sys.argv)>2): bits=int(sys.argv[2]) m = bytes_to_long(msg.encode('utf-8')) p= Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) q= Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) N=(p**2) *q PHI=lcm((p-1),(q-1)) d=(libnum.invmod(N, PHI)) e=N PHI=(p-1)*(q-1) enc=pow(m,N,N) dec=pow(enc,d,p*q) print("--- Schmdit-Samoa public key ---") print("--- Public key ---") print("N=",N) print("--- \nPrivate key (%d-bit primes) ---" % bits) print("p=",p) print("q=",q) print("\n----Encryption----") print("Cipher:",enc) print("Decrypted:",long_to_bytes(dec))
A sample run is:
--- Schmdit-Samoa public key --- --- Public key --- N= 726055074941862718187414169545036076514950414235948991 --- Private key (60-bit primes) --- p= 927835903461470573 q= 843387611753839079 ----Encryption---- Cipher: 651533497450378175352377554005670624374687374340363877 Decrypted: hello
Reference
Schmidt-Samoa, K. (2006). A new rabin-type trapdoor permutation equivalent to factoring. Electronic Notes in Theoretical Computer Science, 157(3), 79-94.