August 2013 - mathfun@mailman.xmission.com

[math-fun] encryption algorithms...
by Warren D Smith 19 Aug '13

19 Aug '13

It looked like TEA, XTEA, XXTEA, and RC5 all were designed to try to be "tiny". However, the sad fact is, that RC5 and TEA both were broken. So evidently, the history of tiny cryptosystems is not a happy one. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] a simple/stupid point about AES and other block cryptosystems
by Warren D Smith 19 Aug '13

19 Aug '13

If you use a system with block size 128 bits (say) that is 16 bytes. If you encrypt a character stream (1 char = 1 byte) going block by block (same key each block) then you are going to repeat if and when author repeats a 16-character phrase. For example, the phrase "Adam P. Goucher\n" where \n is the newline character, occurs often if we were encrypting the math-fun archives. BZZZZ. This indicates to me, despite my complaining before about just XORing text with output of a secure psu-random stream, that this XOR approach should be COMBINED with the block-by-block approach. This is a simple/stupid point, but I have not seen it mentioned in crypto manuals! -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 2

[math-fun] cryptosystem speed comparison (theory)
by Warren D Smith 18 Aug '13

18 Aug '13

>What about RSA (as a simple cryptosystem)? --Too slow or insecure. Say you are encrypting N-bit message using N-bit key. Then the following time and security formulas hold approximately for N large (ignoring constant factors and sometimes log factors). "Fast" denotes fast FFT-based arithmetic. "Security" is kind of a guess, not proven at least until we know P unequal NP. SYSTEM....TIME.....SECURITY slowRSA........N^3............N^(1/3) fastRSA........N^2*logN.....N^(1/3) slowECC.......N^3.............N^(1/2) fastECC........N^2*logN.....N^(1/2) Feistel...........N^2*logN......N I said for my question I did not care about speed so much... but you've got to be in the right ballpark on speed. I'll forgive a factor 10 or even 100 speed loss -- but squaring or cubing the runtime to reach same security level, that seems too much.

2 2

[math-fun] Goucher's suggested cryptosystem
by Warren D Smith 18 Aug '13

18 Aug '13

--I slightly edit plus add comments to Goucher's message repeated below. To Warren, Use a N-bit key to seed a Blum-Blum-Shub pseudorandom number generator, and XOR its output with the message. That's much quicker than RSA (multiplication is faster than modular exponentiation) and far more secure. Time to encrypt/decrypt = O(N log N log log N) * (length of message) Time to brute-force = O(2^N) In pseudocode, we have: -------- p,q,r = N-bit long primes (N=1024 should suffice) distinct primes of the form 4k+3, derived from the key by a deterministic process. M = p*q Repeat{ XOR 32 bits of plaintext with (r mod 2^32) to produce 32 bits ciphertext Let r := r^2 mod M; Once the entire plaintext is processed, exit this loop. } -------- It's cryptographically secure, as even complete knowledge of the state of PRNG would not allow previous states to be computed, thanks to the difficulty of integer factorisation. It's also a very good PRNG, with no obvious patterns in its output. Hence, even if your nemesis has a crib and XORs it with the ciphertext to obtain some of the PRNG output, he/she will still have great difficulty extrapolating. Also, there's the convenience that the algorithm is symmetric for encryption and decryption. --Adam P. Goucher --WDS: elegant. Really, though, this is a PRNG (psu-random number generator) not a cryptosystem. I realize you can misuse it as a cryptosystem, but that sacrifices the usefulness of having an Encrypt(Message,Key) box which is a useful primitive for doing other stuff. Also with Goucher's system if you re-use the same key for a different message, you are dead (kind of like one-time pads only work once). Also, with Goucher's system the preprocessing time (to determine p,q from key) is rather large, maybe of order N^4, motivating people to choke by re-using old key for a new message. Also, by the way, I think to get theoretical nirvana with BlumBlumShub you must only use one bit of r at a time, not 32 bits (right?) costing a factor 32 work. The time consumption here seems to be with fast multiplication about N^2 * logN ops per plaintext bit which for N bit message and key would be N^3 * logN. (And slower if use slow multiplication.) The security level is around N^(1/3) considering NFS integer factoring algorithm. So... asymptotic-wise, this sucks, it is even worse than everything I said before! Elegance-wise, it is very neatly defined.

1 1

[math-fun] meaning of "security level=S" for cryptography
by Warren D Smith 18 Aug '13

18 Aug '13

It means breaking it is presumed to be about as hard as performing 2^S encryptions. For an S-bit secret key, security level S is the best one can hope for.

1 0

Re: [math-fun] cryptosystem speed comparison (theory)
by Adam P. Goucher 18 Aug '13

18 Aug '13

It appears to be the logarithm of the time taken to break into the cryptosystem without prior knowledge of the key. For example, it takes O(exp(N^(1/3))) time to break RSA with the General Number Field Sieve. O> --> O/ Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Eugene Salamin > Sent: 08/18/13 05:23 PM > To: math-fun > Subject: Re: [math-fun] cryptosystem speed comparison (theory) > > Warren, what do you mean by "security level" ? > > -- Gene > > > > >________________________________ > > From: Warren D Smith <warren.wds(a)gmail.com> > >To: math-fun(a)mailman.xmission.com > >Sent: Saturday, August 17, 2013 9:08 PM > >Subject: [math-fun] cryptosystem speed comparison (theory) > > > > > >>What about RSA (as a simple cryptosystem)? > > > >--Too slow or insecure. > >Say you are encrypting N-bit message using N-bit key. > >Then the following time and security formulas hold approximately for N > >large (ignoring > >constant factors and sometimes log factors). "Fast" denotes fast > >FFT-based arithmetic. > >"Security" is kind of a guess, not proven at least until we know P unequal NP. > > > >SYSTEM....TIME.....SECURITY > >slowRSA........N^3............N^(1/3) > >fastRSA........N^2*logN.....N^(1/3) > >slowECC.......N^3.............N^(1/2) > >fastECC........N^2*logN.....N^(1/2) > >Feistel...........N^2*logN......N > > > >I said for my question I did not care about speed so much... but > >you've got to be > >in the right ballpark on speed. I'll forgive a factor 10 or even 100 > >speed loss -- > >but squaring or cubing the runtime to reach same security level, that seems > >too much. > > > >_______________________________________________ > >math-fun mailing list > >math-fun(a)mailman.xmission.com > >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] Always off topic; always on target
by Whitfield Diffie 18 Aug '13

18 Aug '13

NSA has posted a paper on lightweight block ciphers at: http://eprint.iacr.org/2013/404.pdf Whit

2 1

[math-fun] secret key cryptosystem?
by Warren D Smith 18 Aug '13

18 Aug '13

> From: Mike Stay <metaweta(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] secret key cryptosystem? > Pick some keyed nonlinear function of 64 bits to 64 bits, then do a > 500-round Feistel cipher. It's pretty straightforward to get decent > secret-key encryption; the tricky part is doing it quickly. --now you are thinking more like I was thinking. (Albeit 64 bits seems small.) But, has anybody done that sort of thing and done it well? --Also, your other suggestion of ThreeFish is better than AES in the sense that this https://github.com/bmalkow/java-bc-threefish/tree/master/src says it implements it in only 390 lines. Albeit I'd like to get below 100 lines. (Also I want high portability.)

3 2

Re: [math-fun] secret key cryptosystem?
by Adam P. Goucher 18 Aug '13

18 Aug '13

Warren, Use a N-bit key to seed a Blum-Blum-Shub pseudorandom number generator, and XOR its output with the message. That's much quicker than RSA (multiplication is faster than modular exponentiation) and far more secure. Time to encrypt/decrypt = O(N log N log log N) * (length of message) Time to brute-force = O(2^N) In pseudocode, we have: -------- p,q,r = large (1024-bit should suffice) distinct primes of the form 4k+3, derived from the key by a deterministic process. M = pq Repeat the following code: { Take 32 bits of plaintext, and XOR with (r mod 2^32) to produce 32 bits of ciphertext. Let r := r^2 mod M Once the entire plaintext is processed, exit this loop. } -------- It's cryptographically secure, as even complete knowledge of the state of PRNG would not allow previous states to be computed, thanks to the difficulty of integer factorisation. It's also a very good PRNG, with no obvious patterns in its output. Hence, even if your nemesis has a crib and XORs it with the ciphertext to obtain some of the PRNG output, he/she will still have great difficulty extrapolating. Also, there's the convenience that the algorithm is symmetric for encryption and decryption. Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Warren D Smith > Sent: 08/18/13 02:26 AM > To: math-fun > Subject: [math-fun] secret key cryptosystem? > > Any recommended secret-key cryptosystems? > > My desiderata are simple+short algorithm and high security level. > Speed is not very important. > > > -- > Warren D. Smith > http://RangeVoting.org <-- add your endorsement (by clicking > "endorse" as 1st step) > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] secret key cryptosystem?
by Warren D Smith 18 Aug '13

18 Aug '13

Any recommended secret-key cryptosystems? My desiderata are simple+short algorithm and high security level. Speed is not very important. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

4 3