Sysepub: Symmetric semi public key algorithm!


One time pad (o.t.p) with random key are known to be perfect cryptographical systems. Using a pseudo-random key is more practical, but not perfect anymore. So these apparently very good system have at least 3 big weaknesses or limitations:

- The key must be as long as the plaintext, and sending it may cause the same problems of sending the plaintext (limitation of the random o.t.p)

- The pseudo-random generator is periodic in general (weakness)

- The pseudo-random o.t.p. is subject to the plaintext attacks; if someone gets a portion of plaintext he could find out the key (weakness)

My effort is about trying to eliminate these weaknesses and limitation in the following way.
Encryption is performed in 3 main steps.
Let's call A the sender and B the receiver.
- step 1: The plaintext is prepared for encryption. I add at the beginning and at the end of the byte array of plaintext (let's call it x) a short secret byte array (let's call it pattern), then I add two random arrays of random length (the default in Sysepub is 2*x.length at most). The random arrays add very little computational time for the legitimate users, and they complicate cryptanalysis (cryptanalyst won't know WHERE is the real message within x1) especially in a plaintext attack.
- step 2: Here comes out the "public" key. The byte array obtained in step 1 (x1) is XORed with a random byte array. Why it's public? Because, for example, A could generate it in a truly random way, and send it to B even with the ciphertext! But the real key in step 2 isn't exactly the public array pubKey, that must be longer than x1, but a subset of pubKey. This subset is the array realKey obtained from the elements: pubKey[pr] .. pubKey[pr+x1.length] . The positive integer pr < pubKey.length-x1.length is obtained from a pseudo-random generator whose seed is the secret key shared with B.
- step 3: the ciphertext obtained (x2) is XORed with a pseudo-random sequence (prs) obtained from the same pseudo-random generator (or a new one, but you will need another secret seed). Algorithm graph
The byte array x3 obtained is the final ciphertext and can be sent with the public key to B. Now let's see how B deciphers it.
- step 1: B deciphers x3 and gets x2, as he has the secret seed and he can generate the pseudo-random sequence.
- step 2: now B can compute pr with the secret seed; hence he can obtain the real key from pubKey, and so obtains x1.
- step 3: B easily obtains x from x1 searching for the secret pattern.

Why I think this system is innovative.

The limitation of the random o.t.p. is solved: the secret key is in fact very short (the seed and the pattern require few bytes) and must be shared between A and B only one time.
The periodicity of the pseudo-random generator isn't anymore a problem: even if, in time, the same sequence should occur again, the realKey would be different every time and cryptanalisys made more difficult.
The plaintext attack : this is the critical point, where I conjecture that this system is immune to. Thus, suppose that the enemy C has one, or more, pairs of plaintext/ciphertext (x,x3). Now, suppose also that he knows pubKey: he could XOR x3 with every possible subset of length x3.length. With pubKey.length - x3.length = 500 K this means 500000 possible texts xp that, knowing the secret seed, would lead to x. Now what kind of cryptanalysis C could do? That is the question. I conjecture that all the, say 500000 xp, have the same entropy, coming from the pseudo-random sequence x3 (x1 XOR realKey XOR prs), XORed with 500000 truly random sequencies. Moreover, C has x, not x1, and this makes grow on the number of possible realKeys.
I made a statistical test using the ent program (http://www.fourmilab.ch/random/) using a plaintext of 315 K identical bytes; Sysepub enciphered it into a 829KB file. The results were very good (I guess): optimum compression, 0% ; mean value 127.6334 (127.5 = random); Monte Carlo value for Pi is 3.141996862 (error 0.01 percent); Serial correlation coefficient is -0.000079 (totally uncorrelated = 0.0); normal Chi square distribution.

Few words about the Java implementation: it's called Sysepub (acronymous of Symmetric Semi Public ..). As random generator I used the java.util.Random class, probably not really a CSPRNG, but it can be easily substituted by a more cryptographically strong generator in the A1timeP class (the class used as one time pad key generator).


Teutoburgo Home      Sysepub index      Download Sysepub for free!


Copyright Pierre Blanc 2002