Cryptography-Digest Digest #599, Volume #12 Sat, 2 Sep 00 19:13:00 EDT
Contents:
R: R: R: R: R: Test on pseudorandom number generator. ("Cristiano")
R: R: R: R: Test on pseudorandom number generator. ("Cristiano")
Re: Quick, simple and easy cipher? ("James Blythe")
Re: RSA public exponent (DJohn37050)
Re: Quick, simple and easy cipher? (John Bailey)
Re: R: R: R: R: Test on pseudorandom number generator. (Terry Ritter)
I need an algorithm to determine the center of gravity for; ([EMAIL PROTECTED])
Re: R: R: R: R: Test on pseudorandom number generator. ("Trevor L. Jackson, III")
Re: I need an algorithm to determine the center of gravity for; (Erik O. Lyman)
Re: R: R: R: R: R: Test on pseudorandom number generator. (Terry Ritter)
Austin, Tx. - Cypherpunks Physical Meeting (Jim Choate)
Re: New cryption method... (Mok-Kong Shen)
----------------------------------------------------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: R: R: R: R: R: Test on pseudorandom number generator.
Date: Sat, 2 Sep 2000 22:11:11 +0200
> >To test a BBS generator I use some test taken from "Handbook of Applied
> >Cryptography" by A. Menezes, P. van Oorschot and S. Vanstone (including
> >"Maurer's universal statistical test"). These tests seems to be rigth for
> >bits. It is so?
>
> I have the book. Please indicate specifically which tests you mean.
Chapter 5 page 181. All tests in the paragraph "5.4.4 Five basic tests":
Frequency test (monobit test), Serial test (two-bit test), Poker test, Runs
test, Autocorrelation test and Maurer's universal statistical test. (With
Autocorrelation test I found where URAND fail).
> >For my purpose I generate many 1024 bits numbers (with BBS), I collect
only
> >few lsb from these numbers, I apply SHA-1 every 160 bits collected and I
> >take only differents bit pairs (00 and 11 are discarded, while 01=0 and
> >10=1).
> >If I test this sequence with a bit test (including Maurer), it's ok?
>
> The Maurer test article specifically disclaims use of the test on
> pseudorandom sequences. And, in my experience, the test itself is
> much less sensitive than runs.
Do you mean that Maurer's test is good only for random sequences?
I like this test because it's output is only a chi-square value (not 234
p-values), and then because it is able to detect any "tampering" in the
generator (like an arbitrary change of just few bits every hundreds).
For runs test do you mean the one in the above book?
> >For my curiosity, I test such a sequence with Diehard (ok it's bad!).
> >If I collect more than 4 bits at each step (x=x*x % n) Diehard fail big.
> >If I collect less than 5 bits at each step Diehard is far good. Maurer is
> >almost always good.
> >It seems that some information is given also by Diehard. It is possible?
>
> Sure. But if your sequence fails when you test more than a few bits
> of RNG internal state, your RNG's are "bad" and you need to fix them
> before going on. "Good" RNG's generally pass statistical tests even
> when the tests are performed properly on all of the RNG state.
> (Sometimes, specific tests which correspond to RNG structure will
> detect that structure and fail, and we can't do much about that.)
I do only what is in literature. A BBS generator is a BBS generator!
After many attempts to get a "random" sequence, I seen that in most cases by
appling SHA-1 and de-skewing the result is far good.
For a BBS generator is provable secure to get only lg lg n least significant
bits, but by using SHA-1 I can take more bits. So I'd like to take as many
bits as I can (for speed reasons).
How can I fix this generator?
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: R: R: R: R: Test on pseudorandom number generator.
Date: Sat, 2 Sep 2000 22:11:15 +0200
> >If I collect p-values of Diehard in classes (as a histogram) the result
> >looks like a bell shaped curve.
>
> Something seems wrong here, or perhaps this is just a communications
> problem. If we collect p-values from a statistical test on random
> data, we expect to get between 0 and .5 half the time and between .5
> and 1.0 also half the time. We expect about 1/4 of the results in
> each quartile. We do not expect to get a bell shaped curve from p
> values, although we might well get such a curve from the raw statistic
> itself. If there really are many too many p-value results in the
> center, repeatedly, the test has found a problem.
Following your advice, my choice for PRNG fall in TT800 (do you know?).
It seems to be the best for this: I can seed it with 25 32 bits numbers, it
pass always the several tests and the p-values of Diehard is far flat (many
thanks to Tim Tyler for DiehardC).
This is what I mean for "far flat":
Class center p-values found
0,05 19 ===================
0,15 19 ===================
0,25 22 ======================
0,35 24 ========================
0,45 24 ========================
0,55 28 ============================
0,65 26 ==========================
0,75 16 ================
0,85 21 =====================
0,95 35 ===================================
1,05 0
total p-values= 234
Mean= 0,53492095603436
Min= 0,00165856156182101
Max= 0,998935636154854
std. dev.= 0,284750179144904
std. dev./mean= 53,2321973803197%
KOLMOROGOV-SMIRNOV test of p-values= 0,924584850949655
The shape of this distribution is good?
------------------------------
From: "James Blythe" <[EMAIL PROTECTED]>
Subject: Re: Quick, simple and easy cipher?
Date: Sat, 2 Sep 2000 21:24:22 +0100
My own system sounds rather like the credit card system posted here, which I
am looking at now, at seems promising. Here's mine, for the record:
'MULTIPLY' CIPHER by James Blythe
=================================
The aim of creating this cipher was to bridge the gap between simple fixed
character cipher systems (a=j b=e etc.) and complicated and long-winded
systems such as Solitaire. Therefore the basic key-generator system has been
used, but with a much more simple calculation that only needs about 15
seconds/character to generate the keystream, using a standard scientific
calculator. It is safe to assume this cipher is never going to be used above
a certain level - if security is genuinely a matter of life-and death you'll
be better using somehting like Solitaire - therefore one way that this type
of low-level cipher is frequently cracked is because people use spacings of
words in written messages. Therefore all calculations here are modulo 27
instead of 26 as usual - character 27 is represented by _ and is for the
purposes of the calculation (apart from the first section) just another
character.
Basically speaking, the permutations are 26 x 86(6) or 1.051874811354e+13
(10,518,748,113,540,000) - the strange figure will be explained later. It's
highly decrytpable theoretically, but relies on the fact that a) Anyone with
that computing power and knowledge will have it configured to break much
more complicated ciphers than mine, b) No-one at that level would want to
bother. The simplest way of course is to run get a computer program to run
through every permutation, save the results to a file and then run through a
spellchecker, but it'll still take a long time.
Here it is then. The key consists of a letter (l), followed by six integers
between 10 and 99 (abcdef), excepting 27, 54 and 81. the numerical
equivalent* of l is multiplied by a and b, the result is taken modulo 27 and
is the first keystream letter. That mod 27 result is multiplied by c and d,
the result is taken mod 27 and is the second keystream letter. Ditto e and
f, after which the result mod 27 is put back into a and b. Put into a set of
mathematical calculations:
1. mod 27(b(l x a))= k1
2. mod 27(d(k1 x c))= k2
3. mod 27(f(k2 x e))= k3
4. l = k3
5. Return to Step 1.
If 0 is generated 1 is used in its' place the first time 2 the second etc..
This adds another random element, although it may also be a gaping security
hole. My maths fails me here.
The keystream is generated for as many letters as you have in your message,
and then added onto the numerical equivalent* of the plaintext to generate
encrypted text. To decrypt, the keystream is worked out and subtracted from
the ciphered text (mod 27, of course!)
Simple? Yes. And it's quick. Unfortuanetly my maths isn't up to exploring
every possible backdoor, so I'm unsure how secure it is. If it's crap,
please feel free to tell me.
A 16-character encrypted message is given below, to test the security over
short messages with encrypted spaces. If you crack it send me the decrypt,
or email me to ask for the key.
K_OSXBGMIPDRRISU
*Letters are converted into numbers as shown:
A B C D E F G H I J K L M
1 2 3 4 5 6 7 8 9 10 11 12 13
N O P Q R S T U V W X Y Z _
14 15 16 17 18 19 20 21 22 23 24 25 26 27
===========================================
The numerical equivalent table works on monospaced fonts, so for those using
OE or similar it may look strange. Please don't be too nasty if it's
rubbish. Thanks for the help.
=============================
James Blythe
'Quod sis esse velis nihilque malis'
Martial, Epigrams X.47
[EMAIL PROTECTED]
=============================
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 02 Sep 2000 20:42:17 GMT
Subject: Re: RSA public exponent
The use of a small e for performance is one of the few remaining potential
advantages of using RSA over ECC. ECC private key operations (key pair gen,
signing, etc.) are typically much faster than RSA, even with CRT and etc.
speedups. ECC key sizes and certificates can be MUCH smaller for the same
security level. There are many other advantages.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Quick, simple and easy cipher?
Date: Sat, 02 Sep 2000 21:28:06 GMT
On Sat, 2 Sep 2000 21:24:22 +0100, "James Blythe"
<[EMAIL PROTECTED]> wrote:
>My own system sounds rather like the credit card system posted here, which I
>am looking at now, at seems promising. Here's mine, for the record:
>
Here is the crackscript for the *credit card system* posted earlier.
The language is BC, the Unix long number utility.
a = 8480320057465
b = 11567267856144
#example values of a and b
define g(x,y) {
auto z
z = x
while(z > 1) {
z = y % x
y = x
x = z
}
return(x)
}
# usual inverting function
define i(x,y) {
auto a, z, w
w = y
z = 1
while( x < w) {
a = ( y / x ) + 1
w = x
x = a * x % y
z = z * a % y
}
return(z)
}
Not a lot more is available at:
http://www.frontiernet.net/~jmb184/interests/cryptography/numerical_encryption.html
John
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: R: R: R: R: Test on pseudorandom number generator.
Date: Sat, 02 Sep 2000 21:38:33 GMT
On Sat, 2 Sep 2000 22:11:15 +0200, in <8orlgo$nhr$[EMAIL PROTECTED]>,
in sci.crypt "Cristiano" <[EMAIL PROTECTED]> wrote:
>> >If I collect p-values of Diehard in classes (as a histogram) the result
>> >looks like a bell shaped curve.
>>
>> Something seems wrong here, or perhaps this is just a communications
>> problem. If we collect p-values from a statistical test on random
>> data, we expect to get between 0 and .5 half the time and between .5
>> and 1.0 also half the time. We expect about 1/4 of the results in
>> each quartile. We do not expect to get a bell shaped curve from p
>> values, although we might well get such a curve from the raw statistic
>> itself. If there really are many too many p-value results in the
>> center, repeatedly, the test has found a problem.
>
>Following your advice, my choice for PRNG fall in TT800 (do you know?).
No.
>It seems to be the best for this: I can seed it with 25 32 bits numbers, it
>pass always the several tests and the p-values of Diehard is far flat (many
>thanks to Tim Tyler for DiehardC).
>
>This is what I mean for "far flat":
>
>Class center p-values found
> 0,05 19 ===================
> 0,15 19 ===================
> 0,25 22 ======================
> 0,35 24 ========================
> 0,45 24 ========================
> 0,55 28 ============================
> 0,65 26 ==========================
> 0,75 16 ================
> 0,85 21 =====================
> 0,95 35 ===================================
> 1,05 0
>
>total p-values= 234
>Mean= 0,53492095603436
>Min= 0,00165856156182101
>Max= 0,998935636154854
>std. dev.= 0,284750179144904
>std. dev./mean= 53,2321973803197%
>
>KOLMOROGOV-SMIRNOV test of p-values= 0,924584850949655
>
>The shape of this distribution is good?
I would now look at the weak parts again with additional tests.
Depending upon application, we might want to investigate the mean by
sampling 100 times as many values, to verify that it tightens up
toward 0.50.
I assume the K-S result is a p-value, but 0.92 is a little high: when
any test delivers a p-value over .9 or under .1, I do more testing to
see if that is a "fluke" (an unusual occurrence). Values that extreme
should occur by chance only 1 time in 10, but maybe we just got lucky
this time. I would do at least 2 more tests of this size, and only
stop there if both give more reasonable p-values.
In the process of doing additional tests, I would pay attention to
whether the .75 count is always low or .95 is always high. We seek to
eliminate the possibility that testing actually has found a small but
systematic error that we are almost willing to ignore.
I almost never stop at one test, because real results naturally vary
quite a lot.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED]
Subject: I need an algorithm to determine the center of gravity for;
Date: Sat, 02 Sep 2000 21:44:21 GMT
I need an algorithm to determine the center of gravity for;
Let's say I have a bunch of wooden abc blocks
(cubes, all the same size and weight).
And I can glue as many or as few together
in any shape or direction that I want.
How can I determine where is the center of gravity for that object?
Whether or not that center of gravity touches the object or not.
(Say maybe I want to find the center of gravity of that object so I
could glue it onto a round piece of plexiglass, and it would spin
balanced.)
Or can someone aim me somewhere to find out.
Thanks in advance!
[EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Sat, 02 Sep 2000 18:29:28 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: R: R: R: R: Test on pseudorandom number generator.
Cristiano wrote:
> > >If I collect p-values of Diehard in classes (as a histogram) the result
> > >looks like a bell shaped curve.
> >
> > Something seems wrong here, or perhaps this is just a communications
> > problem. If we collect p-values from a statistical test on random
> > data, we expect to get between 0 and .5 half the time and between .5
> > and 1.0 also half the time. We expect about 1/4 of the results in
> > each quartile. We do not expect to get a bell shaped curve from p
> > values, although we might well get such a curve from the raw statistic
> > itself. If there really are many too many p-value results in the
> > center, repeatedly, the test has found a problem.
>
> Following your advice, my choice for PRNG fall in TT800 (do you know?).
Do you mean MT800? (Mersenne Twister)
>
> It seems to be the best for this: I can seed it with 25 32 bits numbers, it
> pass always the several tests and the p-values of Diehard is far flat (many
> thanks to Tim Tyler for DiehardC).
>
> This is what I mean for "far flat":
>
> Class center p-values found
> 0,05 19 ===================
> 0,15 19 ===================
> 0,25 22 ======================
> 0,35 24 ========================
> 0,45 24 ========================
> 0,55 28 ============================
> 0,65 26 ==========================
> 0,75 16 ================
> 0,85 21 =====================
> 0,95 35 ===================================
> 1,05 0
>
> total p-values= 234
> Mean= 0,53492095603436
> Min= 0,00165856156182101
> Max= 0,998935636154854
> std. dev.= 0,284750179144904
> std. dev./mean= 53,2321973803197%
>
> KOLMOROGOV-SMIRNOV test of p-values= 0,924584850949655
>
> The shape of this distribution is good?
------------------------------
From: [EMAIL PROTECTED] (Erik O. Lyman)
Subject: Re: I need an algorithm to determine the center of gravity for;
Date: Sat, 02 Sep 2000 22:29:30 GMT
[EMAIL PROTECTED] wrote:
>Or can someone aim me somewhere to find out.
Try rec.puzzles.
--
"Erik O. Lyman" is actually 7230 986541 <[EMAIL PROTECTED]>.
0123 4 56789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: R: R: R: R: R: Test on pseudorandom number generator.
Date: Sat, 02 Sep 2000 22:36:05 GMT
On Sat, 2 Sep 2000 22:11:11 +0200, in <8orlgl$nhq$[EMAIL PROTECTED]>,
in sci.crypt "Cristiano" <[EMAIL PROTECTED]> wrote:
>> >To test a BBS generator I use some test taken from "Handbook of Applied
>> >Cryptography" by A. Menezes, P. van Oorschot and S. Vanstone (including
>> >"Maurer's universal statistical test"). These tests seems to be rigth for
>> >bits. It is so?
>>
>> I have the book. Please indicate specifically which tests you mean.
>
>Chapter 5 page 181. All tests in the paragraph "5.4.4 Five basic tests":
>Frequency test (monobit test), Serial test (two-bit test), Poker test, Runs
>test, Autocorrelation test and Maurer's universal statistical test. (With
>Autocorrelation test I found where URAND fail).
I particularly like frequency, runs, and autocorrelation.
Of course, frequency on bits is just two bins; it is just "balance"
which does not give a lot of detail. I normally do not find problems
using a frequency test, but missing frequency problems by not testing
would be appalling.
Runs is still effective on bits.
Autocorrelation can be extremely revealing, but my computation uses
FFT operations. I'm not sure I've ever done it on bits. I am sure I
have never used the statistic given in HAC.
>> >For my purpose I generate many 1024 bits numbers (with BBS), I collect
>only
>> >few lsb from these numbers, I apply SHA-1 every 160 bits collected and I
>> >take only differents bit pairs (00 and 11 are discarded, while 01=0 and
>> >10=1).
>> >If I test this sequence with a bit test (including Maurer), it's ok?
>>
>> The Maurer test article specifically disclaims use of the test on
>> pseudorandom sequences. And, in my experience, the test itself is
>> much less sensitive than runs.
>
>Do you mean that Maurer's test is good only for random sequences?
I mean that he says in his article that the test is only for really
random sequences and not pseudorandom sequences. Shall we use his
test and then ignore what he says about its use?
>I like this test because it's output is only a chi-square value (not 234
>p-values),
Something sounds wrong about that: Your earlier message described a
test with 234 values; that is *not* 234 p-values, or at least it
should not be. Those values into one test produce a statistic which
has a p-value -- that is, one p-value -- not 234.
The output of even something very simple like the frequency test is a
statistic which has one p-value, not 234 p-values.
If you have had some success finding problems using the Maurer test, I
would like to hear about it. In my experience, it is very insensitive
at realistic testing sizes, and if we have much more data, the other
tests can use that and improve their results as well.
>and then because it is able to detect any "tampering" in the
>generator (like an arbitrary change of just few bits every hundreds).
Really? What makes you think so?
The Maurer test typically works on bytes, on which runs-up / runs-down
becomes useful. In my experience runs is more sensitive, so I would
expect it to better detect tampering. If that expectation is wrong, I
would like to hear about it.
>For runs test do you mean the one in the above book?
I started implementing statistical tests and testing RNG's a decade
ago, way before HAC, and I have used many different references. One
good reference is Knuth's "The Art of Computer Programming," Vol. 2.
Now that I look at the test descriptions in HAC, they seem pretty
sparse to me, and rather obscure as well.
I do not use the HAC statistic for runs; it seems to me that runs
should have a combinatoric (probably binomial) distribution, and
knowing that, we can collect a distribution of run-length counts, then
compare the sample distribution to the expectation using chi-square.
To me, that would seem to be much more straightforward, more likely to
be programmed correctly, and more useful if it finds a problem. In my
experience, comparing distributions in this way can pick up a
surprisingly wide variety of problems.
>> >For my curiosity, I test such a sequence with Diehard (ok it's bad!).
>> >If I collect more than 4 bits at each step (x=x*x % n) Diehard fail big.
>> >If I collect less than 5 bits at each step Diehard is far good. Maurer is
>> >almost always good.
>> >It seems that some information is given also by Diehard. It is possible?
>>
>> Sure. But if your sequence fails when you test more than a few bits
>> of RNG internal state, your RNG's are "bad" and you need to fix them
>> before going on. "Good" RNG's generally pass statistical tests even
>> when the tests are performed properly on all of the RNG state.
>> (Sometimes, specific tests which correspond to RNG structure will
>> detect that structure and fail, and we can't do much about that.)
>
>I do only what is in literature. A BBS generator is a BBS generator!
Perhaps. But a BB&S generator with small N is insecure. And a BB&S
generator with an error in implementation is not really BB&S at all.
Is a BB&S generator which does not function as one might expect also a
BB&S generator?
>After many attempts to get a "random" sequence, I seen that in most cases by
>appling SHA-1 and de-skewing the result is far good.
But you should not have to do that if the underlying generator is
working right. The need to "de-skew" should tell you that something
is wrong! Maybe a BB&S generator is *not* a BB&S generator! Finding
and resolving this sort of result is exactly why we test!
>For a BBS generator is provable secure to get only lg lg n least significant
>bits, but by using SHA-1 I can take more bits.
Really? Who says?
If you take more bits, you violate the strength theory of BB&S; if you
are willing to do that, why not use the whole BB&S state in SHA-1?
>So I'd like to take as many
>bits as I can (for speed reasons).
>How can I fix this generator?
If you want to find and fix problems in random generators, statistics
is your friend.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Jim Choate)
Subject: Austin, Tx. - Cypherpunks Physical Meeting
Date: 2 Sep 2000 17:49:11 -0500
Sep. 12, 2000, 7-9 pm
Central Market HEB Cafe
38th & N. Lamar
http://einstein.ssz.com/cdr/
We usualy meet outside unless the weather is inclement. Look for the
red covered "Applied Cryptography" book to identify the table.
--
____________________________________________________________________
He is able who thinks he is able.
Buddha
The Armadillo Group ,::////;::-. James Choate
Austin, Tx /:'///// ``::>/|/ [EMAIL PROTECTED]
www.ssz.com .', |||| `/( e\ 512-451-7087
-====~~mm-'`-```-mm --'-
--------------------------------------------------------------------
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 03 Sep 2000 01:17:55 +0200
PROdotes wrote:
>
> Well... the pseudo-code won't be necessary I guess... I gave an rude
> description of the algorithm in the last post I made... To be "more
> precise" the whole algorithm works as one big scrambler. Imagine it as if
> when you take a pega out of the newspaper, cut out some parts and
> reasamble them. And the whol thing goes on and on till the finest level
> is reached... there you scramble some more and do some binary
> transformations. That's about it.
I am sorry to say that a description of the above kind is
much too vague for a proper discussion. For to be able to
clearly know how the bits of the plaintext are processed
to become the ciphertext, one needs far more detailed
informations than an analogy of cutting out a newspaper
and reassmbling the pieces. (There are a multitude of
different ways of cutting and reassembling, isn't it?)
It's a matter of whether you earnestly wish to have some
input from readers of this group or not. If yes, you have
to spend some time and effort to describe your algorithm
in such a way that others could, in principle, write a
program that does exactly what you have in mind. It is
common experience that the chance of obtaining useful
comments/critiques is in general positively correlated
to the quality of description of the algorithm that is
presented to the group.
Another point is that you should avoid posting ciphertexts
obtained from your algorithm, which I suspect you intended
to do with the two new threads. For nobody has the time,
interest and energy/resources to attempt to decrypt such
stuffs output from an unknown algorithm.
Hope that the above is of some use to you.
M. K. Shen
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
