Schmidt-Samoa Encryption
Geometry enlightens the intellect and sets one’s mind right. Ibn-Khaldun
Hey everyone,
Today I want to write a blog about interesting cryptography system called → Schmidt-Samoa encryption.
First of all, let me introduce what cryptography means.
Content
0x00. Cryptography
0x01. Chinese Remainder
0x02. Schmidt-Samoa Encryption Methodology
0x03. Application Theorem with An Example
0x04. python implementation RSA
Cryptography
In the past decade, cryptography has done more to damage the security of digital systems than it has to enhance it. Cryptography burst onto the world stage in the early 1990s as the securer of the internet.Some saw cryptography as a great technological equalizer, a mathematical tool that would put the lowliest privacy-seeking individual on the same footing. Today we will be informing about Schmidt-Samoa encryption as well as decryption technique. Now lets kick off.
Chinese Remainder
Before diving into Schmidt-Samoa Encryption Algorithm, it might be useful to have to have at least basic understanding of Chinese Remainder. I will try to illustrate Schmidt-Samoa Encryption and Decryption Methodology. If you are ready to learn and applicate its in the modern life that should be awesome to securely encrypt your messages.
The original Chinese Remainder Problem (CRP) proposed by Sun Zi in Sun Zi Suanjing , which consists of three volumes, is as follows:
“We have a number of things, but do not know exactly how may. If we count them by threes we have two left over. If we count them by fives we have three left over. If we count them by sevens we have two left over. How many things are there?”
Awesome, we need to applicate this in a mathematical manner.
In modern terminology the problem is to find an x such that
x = 2 mod 3
x = 3 mod 5
x = 2 mod 7
Sun Zi solved the problem as follows. The first step is to compute a value for the following S1 , S2 and S3
S1 = 0 mod 5 = 0 mod 7 = 1 mod 3, S2 = 0 mod 3 = 0 mod 7 = 1 mod 5, S3 = 0 mod 5 = 0 mod 3 = 1 mod 7.
He took:
S1 = 70,
S2 = 21
S3 = 15.
Since 5 and 7 divide so, S1 must be of the form 7 x 5 x k = 35/c , where k is an integer. Hence S1 mod 3 = 2k mod 3, and k = 2 gives S2 = 70. S1 and S2 were similarly computed. The second step is to compute
S’1 = 2S1 = 140,
S’2 = 3S2 = 63,
S’3 = 2S3 = 30.
The last step is to compute x = S’1 + S’2 + S’3 mod (105) = 23.
The solution was explained with a verse later in Cheng Dawei’s book Suanfa Tongzong (A Collection of Algorithms, 1593).
If you want to be more informed about this Remainder Theorem. Please check this out.
Schmidt-Samoa Encryption Methodology
We know that IOT, clouds, network communication, and telecommunications systems hence, the message which people in the world are using to communicate to each other are being encrypted to securely communicate with people around the world. In the last decades, we are facing some vulnerabilities to interrupt people and companies to hack them however, it is not what we see because cryptography, provides the secure communication networks by a means of cryptographic primitives
Awesome, we understood that the messages are being sent with kind of cryptic algorithms to secure the messages. Today, we are going to talk about Schmidt-Samoa cryptography.
the Schmidt-Samoa cryptosystem is an asymmetric cryptographic technique like Rabin system, but it has some differences like; Rabin Algorithm, the public key in the Rabin cryptosystem is n; the private key is the tuple (p,q), everyone can encrypt a message using n; only Bob can decrypt the message using p and q . Decryption of the message is infeasible for Anna because she does not know the values of p and q. When we cover about Schmidt-Samoa
First of all, let me demonstrate the key generation of this algorithm. We assume that “N” is the public key and “D” is the private key. P and Q large distinct primes should be chose by the user to generate the key. The expression is given below
N=P2.Q
so, D will be generated by:
As we follow, that N is the public key, and D is the private key
for more info check this video –> https://www.youtube.com/watch?v=9CUmwD6SSZY
Encryption
So, we have N and D right? Lets decrypt our ciphertext
We are going to encrypt our ciphertext
Decryption
We already know D, now we will compute our ciphertext to decrypt the message
is given to decrypt it. Chinese Remainder is already given.
Application Theorem with An Example
We are going to demonstrate P = 7 and Q = 11 thus N=P2.Q=539
3-) LCM(6,10) = 30
4-) we need to add continuously + 30 until its a whole integer for instance,
(1/539) + 30 (x) k — –> k = 521 because 30 x 521 = 15630 and (+1) = 15631 is divisible by 539
5-) 15631/539=29
6-) D = 29 –> Decrypt
7-) Now we are going to decrypt the cipher: M = 32 ,
we will want to verify it –>
I had already proven this by my own however, you can also check it again –> https://en.wikipedia.org/wiki/Schmidt-Samoa_cryptosystem
Python implementation RSA
Now lets have fun. We will be using Schmidt-Samoa. Go to Schmidt-Samoa to implement and git the repository to your machine.
As you can see, we easily generated our privkey, pubkey.
def generateKey(n):
p, q = getPrime(n), getPrime(n) # lets say p = 7 and q = 11 from getPrime
n = p * q # it will generate our N. N = 11.7
pk = pow(p, 2) * q # we will compute pk with $$p^2*q$$ thus $$7^2.11$$
sk = inverse(pk, lcm(p - 1, q - 1)) # and we it will generate sk value with inverse function .
return(pk, (sk, n)) # return it.
def getPrime(n):
number = random.getrandbits(n) # we got n value from the user. It will generate random number
round = prime.getRound(n) # And it will be rounded to round value
while prime.miller_rabin(number, round) != True: # I have already written a blog about Miller-Rabin thus take a look (if not true then)
number = random.getrandbits(n)
return number # return number
Get Prime in Python
You can easily generate a prime number through Python code. will be useful to use it because the important part of this algorithm is using distinct large prime number to encrypt our messages.
encrypt function in Python
import base64
def encrypt(message, pk):
"""
cipher = [] # our cipher
for char in message.encode():
newval = str(pow(ord(char), pk, pk)) + " "
cipher.append(newval)
return base64.b64decode(''.join(cipher).strip().encode())"""
return base64.b64encode(''.join([str(int(pow(ord(char), pk, pk))) + " " for char in message]).strip().encode())
Algorithm of this encrypted function:
- it Chooses next character of my string(message)
- You remember ASCII table in C ( it Gets the numeric equivalent of each character)
- The string will be encrypted one by one
- while this working it returns to step 1
- After this process , it will be encrypted in base64
decrypt function in python
def decrypt(cipher, sk, n):
"""
plain = []
for num in base64.b64decode(cipher).split(" "):
newval = str(chr(pow(num, sk, n)))
plain.append(newval)
return ''.join(plain)"""
return ''.join([str(chr(pow(int(num), sk, n))) for num in base64.b64decode(cipher).split(" ")])
- Cipher will be decoded in base64
- it separates the spaces in my cipher
- each spaces will be Mathematically processed the reserved place in my cipher to be identified
- it shall be combined together
decrypt our creepy message
Conclusion
If you were unable to understand this mindset, please ask me for the help…
Thank you for spending your valuable time for this content. I will see you in the next time. More awesome blogs will be written!!
You can follow on:
LinkedIn: https://www.linkedin.com/in/ahmetgoker
Twitter: https://twitter.com/TurkishHoodie_
Instagram: https://instagram.com/oxcd4_