Schmidt-Samoa encryption [EN]

0x00. Cryptography
0x01. Chinese Remainder
0x02. Schmidt-Samoa Encryption Methodology
0x03. Application Theorem with An Example
0x04. python implementation RSA

“”Geometry enlightens the intellect and sets one’s mind right.”” ― Ibn-Khaldun

Cryptography

In the past decade, cryptography has done more to damage the security of digital systems than it has to enhance it. Cryptograpy 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 and 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 –> Chinese Remainder

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 cryptograpy, 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 cryptograpy.

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 cryptosytem 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=P^2.Q\) so, D will be generated by:

\[D=N^{-1} mod lcm (P-1, Q-1)\]

As we follow, that N is the public key, and D is the private key

for more info check this video –> Schmidt-Samoa

Encryption

So, we have N and D right? Lets decrypt our ciphertext

\(C = M^N mod N\). We are going to encrypt our ciphertext

Decryption

We already know D, now we will compute our ciphertext to decrypt the message

\(M=C^D mod P.Q\) is given to decrypt it. Chinese Remaider is already given thus,

Application Theorem with An Example

We are going to demonstrate P = 7 and Q = 11 thus \(N=P^2.Q=539\)

1-) \(N=D^-1 mod lcm(P-1, Q-1)\)

2-) \(D= 539^{-1} mod lcm(6,10)\)

3-) lcm(6,10) = 30

4-) we need to add continously + 30 until its a whole integer for instance,

$$(1/539) + 30 x k —–> k = 521 because 30 x 521 = 15630 and (+1) = 15631 is divisble by 539

5-) \(15631/539 = 29\)

6-) D = 29 –> Decrypt

7-) Now we are going to decrypt the cipher: M = 32 ,

\(C=M^N\), \(C=32^29 mod 29 = 373\)

we will want to verify it –> \(M = C^D\), \(32 = 373^29 modP.Q\) P–> 7, Q–> 11

\[(M)32=373^29 mod 7.11 = 32\]

I had already proven this by my own however, you can also check it again –> Schmidt-Samoa

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.

import schmidtSamoa as SS

dir(SS)

[‘all’, ‘builtins’, ‘doc’, ‘file’, ‘name’, ‘package’, ‘path’, ‘core’, ‘decrypt’, ‘encrypt’, ‘generateKey’, ‘key’, ‘prime’]

in the third step, you can see that we list the function which can be used.

(I am going to use “generate”) pubkey, privkey = SS.generateKey(8) (pubkey, privekey will be generated)

privkey

privkey

(17L, 215L) pubkey

pubkey

9245L

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
       

GetPrime 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 our message

We defined yet a string called “darkghost” lets take look to these steps

import schmidtSamoa as SS

pubkey, privkey = SS.generateKey(8)

creepy = “darkghost”

creepy = SS.encrypt(creepy,pubkey)

the output

OTQ5IDUzNDkgNTMyNiA1MzI2IDcgMjI2’

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 encrypt function

1. it Chooses next character of my string(message)
2. You remember ASCII table in C ( it Gets the numeric equivalent of each character)
3. The string will be encrypted one by one
4. while this working it returns to step 1
5. 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(" ")])
  

1. Cipher will be decoded in base64
2. it separates the spaces in my cipher
3. each spaces will be Mathematically processed the reserved place in my cipher to be identified
4. it shall combine together

decrypt our creepy message

import schmidtSamoa as SS

pubkey, privkey = SS.generateKey(8)

creepy = “darkghost”

creepy = SS.encrypt(creepy,pubkey)

creepy ‘OTM3NjEgNTQ3MDg1IDMxODI2MCA0MzEwOTkgMzU3NDUyIDM1MDIgMTY2MzUgOTczNDcgMzY1Nzc3’

hack = SS.decrypt(creepy, privkey[0], privkey[1])

hack darkghost

So we are done with this implementation.

Conclusion

If you were unable to understand this mindset, please ask us for 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!!

Ahmet Göker