Sysepub: Symmetric semi public key algorithm!

Introduction
Plaintext attack

One time pads (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). Sysepub 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. First of all let's see how it can be successfully made in the simple case of pseudo-random o.t.p.
The plaintext attack for pseudo-random one time pads
In this case, if an enemy C could get a long enough portion of plaintext with the ciphertext, he could find out with a simple XOR the key generated by the PRNG initialized with the secret seed. The graph shows what C has got to do: knowing what PRNG was used, he could easily generate the pseudo-random output, until the exact sequence of the key is found. Now he could easily decrypt other ciphertext enciphered with the same system: for example if A and B simply used every time the next bytes generated by the PRNG, all that C has to do is to take the next ciphertext and, eventually making some shifts, XORing with the next pseudo-random bytes. That's why pseudo-random o.t.p are risky.
Now, let's see why I believe Sysepub is much more strong against plaintext attacks. The unknowns in a plaintext attack against Sysepub
Suppose that 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. Attempts to make a plaintext attack
C could take a xp and XOR it with x to try obtaining the prs: but xp is longer than x, so he should try every subset of xp of the length of x; and so on, for every xp obtained. Moreover C could even obtain multiple sequences compatible with the PRNG output. In conclusion the computational time is much greater than the simple case of psudo-random o.t.p. To make an evaluation I'll refer to the
Sysepub challenge example. Let's call t the time needed to perform the plaintext attack in the simple case. In the challenge the plaintext is of 56 KB, the ciphertext of 194 KB and the pubKey of 200 KB. So there are nearly 6000 possible xps, and for each of them, if he is unlucky, C must try nearly 138000 subsets of the length of x. Then the computational time is 6,000*138,000*t = 828,000,000*t in the worst case.

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      Sysepub help


Copyright Pierre Blanc 2002