August 2013 - mathfun@mailman.xmission.com

[math-fun] RSA as "one time pad"?
by Warren D Smith 20 Aug '13

20 Aug '13

> WDS:no, it (RSA for secret key use) is a secret key cryptosystem. It is > much more secure against repeated use, than a 1-time pad. I just > pointed out, it is much less secure than > the usual secret key systems are generally thought to be. >Mike Stay: If M is public, then E is a one-time pad. --no. If modulus M is public, E secret, and I send x^E mod M as encrypt of message x, then I send y^E mod M as encrypt of message y, then there is no easy way to determine E even for an attacker who knows x and y. And if attacker knows only x, no easy way to determine y or E. So this is much safer than a 1-time pad. But can determine E by solving discrete log problem, so weaker than usual secret key cryptosystems. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Simply recursively described secret key cryptosystem
by Warren D Smith 20 Aug '13

20 Aug '13

> MIke Stay: That's not RSA, that's just a strange one-time pad. --no, it (RSA for secret key use) is a secret key cryptosystem. It is much more secure against repeated use, than a 1-time pad. I just pointed out, it is much less secure than the usual secret key systems are generally thought to be. > At this point, it seems to me this has become a discussion for sci.crypt. You'll need to post your own cryptanalysis with the design (e.g. prove it's secure against differential, linear, saturation, boomerang, and whatever number-theoretic attacks you can come up with), as well as explain why anyone should care about it. --the recursive system I described was more a skeleton of a design, than a design. I have no idea how secure it is against those attacks. The reason anybody should care about it, is this skeleton permits the design of very simple cryptosystems. Can you be more precise about what "sci.crypt" is?

2 1

[math-fun] Simply recursively described secret key cryptosystem
by Warren D Smith 20 Aug '13

20 Aug '13

Here's one, I wonder if anybody can point out weaknesses in it. I will describe a cryptosystem for encrypting/decrypting N-bit messages using N-bit secret key in O(N^2) steps where N must be a power of 2. (For non powers of 2, pad message with 0s or something until reach next power of 2 size?) Call the encryption function F(N, message, key). If N<=64, then use some particular well chosen cryptosystem, as base case. If N>64 then split the message m into two halves A,B, each N/2 bits long and similarly split the key k into two halves X,Y, and then F(N, m, k) is then got by A = A xor F(N/2, B, Y) B = B xor F(N/2, A, X) A = A xor F(N/2, B, X xor Y) B = B xor F(N/2, A, X - Y mod 2^(N/2)) transforms the message into ciphertext in place. Doing the 4 steps in reverse order decrypts. The 2 magic xor and - combining methods could be replaced with something else if you preferred (the ones I chose seem poor in sense they do not mix up bits much). If you wanted a bit more safety you could, just at the final (largest N) level of the recursion only, iterate the thing J times [where k=log(N) for example] using i to modify the key in each iteration i. That would make scheme J times slower. Is it safe? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Salamin suggestion to use RSA as a secret-key cipher
by Warren D Smith 19 Aug '13

19 Aug '13

E.Salamin claimed if simplicity paramount, using RSA as a secret key cipher (perhaps with a few modifications?) ought to have security exponential in bit length N, not in N^(1/2) or N^(1/3), and it is very easy to describe. At first I thought: there is much to be said for this suggestion. But I think "simplicity" has to be reckoned not merely in terms of mathematical conceptual simplicity, but also in terms of the program size, and effort to verify and fully comprehend the program. --- Anyhow, for this approach: M=p*q is a product of 2 primes p,q; or for this mode we might more simply make M be a prime. Then E and D related by E*D mod EulerTotient(M) = 1 are the two secret keys, E for encrypting, D for decrypting, and a message X is encrypted to X^E mod M, and ciphertext Y is decrypted to Y^D mod M. M is also part of the secret key. M is deducible if attacker has black box access to a cryptor box -- you binary search to see how large allowed to go, to deduce M. One that is done, M can be factored in subexponential time. Also, if know M and have a plaintext-ciphertext pair then can deduce E and D by solving discrete log problem in subexponential time. So... sorry, you lose. This "RSA as secret key cryptosystem" suggestion is breakable in subexponential, not exponential, time, by certain kinds of attacks, whereas, conventional secret key ciphers are thought/hoped immune to all such attacks even in exponential time. ---- However... suppose we instead employ a 4-round Feistel cipher whose frobulation function is a discrete exponential. I.e. divide the message into two halves A and B. Now perform A = A XOR DiscreteExponential(B) B = B XOR DiscreteExponential(A) A = A XOR DiscreteExponential(B) B = B XOR DiscreteExponential(A) and output the new A,B as the ciphertext. (Decrypt by going thru the 4 steps in reverse order.) The exponents in the discrete exponentials will be the secret keys. All will have the same modulus which will be a public constant large mersenne prime, specifically M=2^127 - 1 causing the message to be 127*2=254 bits long where a few "all 0s or all 1s" message-types are forbidden. If 4 general exponents were used this would be 127*4=508 bits of secret key, but if we agree that 2 of the exponents are determined in some simple public way by the other two (e.g, specified linear relations), then only 254-bit-long secret key needed. And I see no way to attack this in subexponential time, albeit perhaps there is some way which takes a smaller exponential that you might have hoped for. This here suggestion, it seems to me, might actually be a good candidate. In terms of conceptual simplicity it is hard to beat, but in terms of either efficiency or program length & effort it seems pretty bad versus rivals. On other hand if language already supports discrete exponentiation so you do not need to program it...

2 2

[math-fun] Fwd: Muffin problem origins
by James Propp 19 Aug '13

19 Aug '13

Can anyone on the list help solve this mystery? Specifically, did any of you either use muffin problem as a homework problem shortly after it was posted to math-fun, or mention it to someone else who might have? Jim ---------- Forwarded message ---------- From: Jeremy Copeland <copeland(a)artofproblemsolving.com> Date: Mon, Aug 19, 2013 at 3:37 PM Subject: Re: Muffin problem origins To: James Propp <jamespropp(a)gmail.com> Cc: Joe Buhler <buhler(a)ccrwest.org>, Gary Antonick <gantonick(a)gmail.com>, Alan Frank <alan(a)8wheels.org> Hi Jim, The data is still inconclusive, but seductive. The earliest use of the problem in our classes seems to be Jan 21, 2009. It looks like the problem initially hit math-fun on Jan 2, 2009 (see below). That's a pretty tight window, but the fact that those are the same month would be a pretty interesting coincidence, given how things like these often flare up, spread, and then dissipate. I don't think we're going to find a smoking gun here, but my money is on Joe's theory. Jeremy >> Date: Fri, 2 Jan 2009 03:17:35 +0000 From: James Propp <jpropp(a)cs.uml.edu> To: "math-fun(a)mailman.xmission.com" <math-fun(a)mailman.xmission.com> Subject: [math-fun] muffin problem Alan Frank (a friend of mine and Andy Latto's) asks, what's the best way to divide m identical muffins among n people, so that each person gets the same amount of muffin (receiving either one piece of size m/n or several pieces whose sizes add up to m/n), where "best" means "so as to maximize the size of the smallest piece". On Sun, Aug 18, 2013 at 4:09 PM, James Propp <jamespropp(a)gmail.com> wrote: > But we know when the problem was discussed on math-fun; doesn't the > homework problem version pre-date that? > > Jim > > > On Sunday, August 18, 2013, Joe Buhler <buhler(a)ccrwest.org> wrote: > > > > Jim et al, > > > > On Sat, Aug 17, 2013 at 08:07:23PM -0700, James Propp wrote: > >> You could say that the problem appears to have been invented > independently > >> by several people, including recreational mathematician Alan Frank. > > > > It seems likely to me (though probably impossible to verify at this > remove > > in time) that the problem ended up at Jeremy through some non-obvious > > ricochet from the math-fun discussion. So that the problem appears to > > have been invented by Alan, though independent discovery can't be ruled > > out. Hard to know how to phrase that exactly. It is a very natural and > > cute problem. > > > > Joe > > > > >

1 0

[math-fun] Does this look familiar?
by Victor Miller 19 Aug '13

19 Aug '13

http://wordplay.blogs.nytimes.com/2013/08/19/cake/?src=recg

1 0

[math-fun] Always off topic; always on target (SIMON and SPECK cryptosystems)
by Warren D Smith 19 Aug '13

19 Aug '13

http://eprint.iacr.org/2013/404.pdf that was interesting - I did not know the NSA published stuff about cryptography. I agree this is simple and short and fast. The bad news is it looks to me like a poorly designed cryptosystem -- I can see very obvious changes which seem highly likely to be major security improvements.

3 2

[math-fun] Why cryptosystems should be tiny
by Warren D Smith 19 Aug '13

19 Aug '13

The difficulty of breaking a typical secret key cipher grows exponentially with key length N. For known public key systems, the growth instead is exponential in N^(1/2) or N^(1/3), which is less useful, but still adequate. But meanwhile, there is another threat: the threat that your crypto-algorithm may not actually be doing what you think, because somebody in the KGB is circulating a spoof crypto-algorithm containing built in "back doors", side effects, or whatever. The difficulty of verifying a program of length L does what it is supposed to (plus does not have unwanted side effects) grows FAR FASTER than exponential with L, in fact faster than any computable function. So therefore, the program length L is actually a security bottleneck. Typical algorithms papers in computer science purporting to prove correctness do so for programs <=1 or 2 pages long. Alleged bug rates in commercial programs range from 0 bugs in 500,000 lines of code (space shuttle) to 1 bug per 20 lines. Microsoft claims to have achieved 1 bug per 2000 lines of released code, which allegedly is comparable to the bug rates in a survey of open-source projects, and which they claim is way better than the industry average which is 1 bug per 20-100 lines. Further, rates of "exploitable" bugs per line of code are believed to exceed about 1 per 10000 lines based on exploit counts and line counts for various systems. All this is for unintentional bugs, not our threat of intentionally introduced and intentionally hidden exploitable bugs, and all those rates were in the absence of intentional $billion efforts to spoof and defeat the software, etc etc. Published crypto-algorithms have historically often been broken. All this suggests that 1. it is completely unacceptable for a cryptosystem to exceed 10000 lines. 2. It is best if it fits in 1-2 pages (<200 lines, 10000 characters). Tinyness matters, even though the vast majority of the crypto community has regarded this as something that does not matter. Compare: "Gnu privacy guard" is a 3.6 megabyte download even in compressed form. If you attempted to verify their code, it would take you a couple man-weeks at the very least just to read it. Very few people are going to perform that effort. Joe Schmoe cryptosystem user would be completely at the mercy of any evil programmers trying to fool him. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

Re: [math-fun] Goucher's suggested cryptosystem
by Adam P. Goucher 19 Aug '13

19 Aug '13

Warren wrote: > 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. What?! Multiplication takes O(N log N log log N), not O(N^2 log N). There's a very big difference. (It only takes one multiplication per loop.) > 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. No, that's unnecessary. The last 32 bits will certainly be uniformly distributed (up to a ridiculously microscopic difference) amongst the 2^32 possibilities, and the significant bits of r will sufficiently mess up any possible patterns between consecutive words outputted by Blum-Blum-Shub. > Also, with Goucher's system the preprocessing time (to determine p,q from key) > is rather large, maybe of order N^4, I can get O(N^3 log N log log N) by naive Miller-Rabin on every value in a range of length O(N), which will on average contain a prime by the prime number theorem. The constant factor can be heavily optimised by using trial division. > (And slower if use slow multiplication.) > The security level is around N^(1/3) considering NFS integer factoring > algorithm. Are you saying that if I gave you a black box oracle capable of constant-time integer factorisation, you could break my cryptosystem? I highly doubt it, since there's no obvious way of determining M from the output of the BBS (which you can in turn only compute if you know both a sequence of ciphertext and corresponding plaintext). > So... asymptotic-wise, this sucks, it is even worse than everything I > said before! Well, you included an extra factor of N in the time it takes to multiply two numbers... > Elegance-wise, it is very neatly defined. Thank you. Sincerely, Adam P. Goucher http://cp4space.wordpress.com

2 2

Re: [math-fun] Solvable, irreducible quintic trinomials
by Bill Gosper 19 Aug '13

19 Aug '13

http://en.wikipedia.org/wiki/Quintic "During the second half of 19th century, John Stuart Glashan<http://en.wikipedia.org/w/index.php?title=John_Stuart_Glashan&action=edit&r…>, George Paxton Young, and Carl Runge<http://en.wikipedia.org/wiki/Carl_Runge>found that any irreducible <http://en.wikipedia.org/wiki/Irreducible_polynomial> quintic with rational coefficients in Bring<http://en.wikipedia.org/wiki/Erland_Samuel_Bring> -Jerrard <http://en.wikipedia.org/wiki/George_Jerrard> form, [image: x^5 + ax + b = 0\,] (x^5+ax+b=0) is solvable by radicals if and only if either *a* = 0 or it is of the following form: [image: x^5 + \frac{5\mu^4(4\nu + 3)}{\nu^2 + 1}x + \frac{4\mu^5(2\nu + 1)(4\nu + 3)}{\nu^2 + 1} = 0] (x^5 + 5*\[Mu]^4*(4*\[Nu] + 3)*x/(\[Nu]^2 + 1) + 4*\[Mu]^5*(2*\[Nu] + 1)*(4*\[Nu] + 3)/(\[Nu]^2 + 1)) where [image: \mu] and [image: \nu] are rational. In 1994, Blair Spearman and Kenneth S. Williams gave an alternative, [image: x^5 + \frac{5e^4( 4c + 3)}{c^2 + 1}x + \frac{-4e^5(2c-11)}{c^2 + 1} = 0.] (x^5 + 5*e^4*(4*c + 3)/(c^2 + 1)*x - 4*e^5*(2*c - 11)/(c^2 + 1)) "In at least two cases where the quintic is reducible, 1/8 (1 + x) (3 - 8 x + 8 x^2 - 8 x^3 + 8 x^4)==0, and 1/3 (1 + x) (8 - 3 x + 3 x^2 - 3 x^3 + 3 x^4)==0 these parameters come out Gaussian rationals: {\[Mu] -> -(1/4) + I/4, \[Nu] -> 1/4 + (3 I)/4} and {\[Mu] -> -(1/2) + I/2, \[Nu] -> -(3/2) - I}, i.e., {e -> -(1/4) + I/4, c -> 1/4 - (3 I)/4} and {e -> -(1/2) + I/2, c -> -(3/2) + I} The quintic solver goes ahead and produces such unlikelihoods as 1/10 ((-79 + 3 I) ((-7 - 24 I) + 3 Sqrt[-41 + 38 I]))^(1/5) + 1/10 ((3 + 79 I) ((7 + 24 I) + 3 I Sqrt[41 - 38 I]))^(1/5) + 1/10 ((3 + 79 I) ((7 + 24 I) - 3 I Sqrt[41 - 38 I]))^(1/5) E^(( 2 I \[Pi])/5) + 1/10 ((79 - 3 I) ((7 + 24 I) + 3 Sqrt[-41 + 38 I]))^(1/5) E^(-((4 I \[Pi])/5)) == 1/4 (1 - (-1)^(3/4) Sqrt[2] 5^(1/4) + I Sqrt[5]) , which embarrasses RootReduce. --rwg > > > -------- Original Message -------- > Subject: [math-fun] Solvable, irreducible quintic trinomials > Date: 2011-11-08 00:44 > From: Bill Gosper <billgosper(a)gmail.com> > To: math-fun(a)mailman.xmission.com > Reply-To: > > The only ones of height<=5 are > x^5 - 5 x^2 - 3, 2*x^5 - 5*x + 4, and 4*x^5 + 5*x + 4 > (modulo x->1/x). The only real root of the 2nd one is > (1/(2^(2/5) 5^( > 3/5)))(-(150 - 100 Sqrt[2] + Sqrt[10 (4250 - 2999 Sqrt[2])])^( > 1/5) + (-150 + 100 Sqrt[2] + Sqrt[10 (4250 - 2999 Sqrt[2])])^( > 1/5) - (150 + 100 Sqrt[2] - Sqrt[10 (4250 + 2999 Sqrt[2])])^( > 1/5) - (150 + 100 Sqrt[2] + Sqrt[10 (4250 + 2999 Sqrt[2])])^(1/5)) > > This seems almost a case of "*a stupid man asking such a question > to which one hundred wise men would not be able to answer*." > > Various sources, e.g., http://en.wikipedia.org/wiki/**Quintic_function<http://en.wikipedia.org/wiki/Quintic_function> > give a pair of equations which have rational roots iff x^5+ax+b > is solvable and irreducible, but sometimes reducible cases that > fail this test, e.g., {3/8 - (5 x)/8 + x^5, 8/3 + (5 x)/3 + x^5}, yield > to the quintic solver, producing obscure radical identities of the form > biquadratic = sum of four fifth roots of biquadratics, which paralyze > FullSimplify. > > I don't know if it's proven or merely conjectured that there are > no solvable irreducible septic trinomials. See > http://www.math.harvard.edu/~**elkies/trinomial.html<http://www.math.harvard.edu/~elkies/trinomial.html> > --rwg >

1 0