Cryptography-Digest Digest #947, Volume #9 Wed, 28 Jul 99 22:13:03 EDT
Contents:
Re: What the hell is XOR? ("Douglas A. Gwyn")
Re: Prime numbers wanted (John Savard)
Re: OK. Maybe I am missing something here. ("Douglas A. Gwyn")
Re: OTP export controlled? ("Douglas A. Gwyn")
Re: With all the talk about random... (John McDonald, Jr.)
Can you use HASH functions for identification? (Michelle Davis)
Re: Prime numbers wanted (Gergo Barany)
Re: Prime numbers wanted (John McDonald, Jr.)
Re: Prime numbers wanted (John Savard)
Re: With all the talk about random... (Mel Yorkian)
Re: What is twofish ??? (Keith A Monahan)
Re: OTP export controlled? (Isaac)
Re: What the hell is XOR? ([EMAIL PROTECTED])
What is twofish ??? (spike)
Thanks for the input on my OTP, what about this? (Shktr00p1)
Re: the defintion of Entropy (Keith A Monahan)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: What the hell is XOR?
Date: Wed, 28 Jul 1999 19:37:26 GMT
John Savard wrote:
> >0 0 1 0 GT (NIMP is like NXOR; meaningful but rude)
> But, of course, I would quibble that TRUE and FALSE aren't numbers;
They're constants in a Boolean algebra. The "GT" is just a name
for the specific binary operation; one can think of other names.
Boole himself actually did operate with 0 and 1 as numbers, using
arithmetic operations; e.g. a AND b <==> a TIMES b. There is an
isomorphism between GF(2) and the standard Boolean algebra, so
there is really nothing wrong with using "arithmetic" (mod 2) in
place of "logic" operations.
While we're on the subject, note that one can encode the binary
Boolean operators by using their truth table as the bits of their
code number. E.g. Cab (a IMPLIES b) has the truth table
a b Cab
0 0 1
0 1 1
1 0 0
1 1 1
so the truth-table entry for C is 1011(binary) (LSB on the right),
which is 0xB or 11(base 10). the advantage of such an encoding
is that the opcode itself contains the result for every combination
of inputs, in a uniform representation that can be realized using
very few wires/gates/operations. This idea generalizes to n-ary
Boolean operators. You could even consider this coding their
(completely specific) name.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Prime numbers wanted
Date: Wed, 28 Jul 1999 19:38:53 GMT
"Vincent" <[EMAIL PROTECTED]> wrote, in part:
>Is there any faster algorithm than the following one, which, given an (odd)
>number n, returns the first prime number p>=n ?
>Assuming that I have a function is_prime tellimg me if a number is (or has
>enough odd to be) prime (The Miller-Rabin test).
>int My_Simple_Algorithm (int n)
>{
> int temp=n;
> while (!is_prime(temp)) temp+=2;
> return(temp);
>}
Actually, there isn't *much* you can do to improve the speed of
finding a prime, but there is a little.
1) Instead of just testing only the odd numbers, you can also skip
testing numbers divisible by 3, by 5, by 7. Since you don't want to
bias the search in favor of primes equal to 1 modulo 210, the logic
gets a _bit_ complicated, but it need not be too bad.
2) You should first test the number using a fast probabilistic
primality testing algorithm. Only numbers that pass such a test should
be subjected to the slower test that ensures that they're prime.
(I'm not an expert on this, so others may give you better
suggestions.)
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: OK. Maybe I am missing something here.
Date: Wed, 28 Jul 1999 19:39:35 GMT
Patrick Juola wrote:
> Kasiski superposition has more general applications than finding
> periodicity; in particular, one can use it to find a twice-used
> OTP.
You must mean the "kappa test". The Kasiski method measures the
linear distance within a single message of repeats, and looks for
a common factor.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OTP export controlled?
Date: Wed, 28 Jul 1999 19:50:03 GMT
Dave Hazelwood wrote:
> It all comes down to every one of us doing our part and not big
> brother doing it for us.
Dave, the problem has been that far too many lazy SOBs prefer to
assign their personal decision making to somebody else, and there
is always somebody who is happy to take it from them. That means
that the rest of us are fighting not only the powermongers, but
also (by proxy) the lazy SOBs. That wouldn't be so bad in a
properly functioning constitutional republic, but in our case the
idea of majority rule has been adopted as some sort of ideal, so
the good guys being outnumbered becomes a serious problem.
It seems to be mostly an educational problem, and guess who has
taken control of our children's education..
------------------------------
From: [EMAIL PROTECTED] (John McDonald, Jr.)
Subject: Re: With all the talk about random...
Date: Wed, 28 Jul 1999 20:41:03 GMT
On Wed, 28 Jul 1999 09:26:19 -0000, "Jeffery Nelson"
<[EMAIL PROTECTED]> wrote:
>What's so bad about C++ or (The dreader, but still valad) BASIC functions
>for generateing random numbers. Are their methods flawed? I know they
>derive them from a list and the time of day, but this seems random ENOUGH to
>not be able to recognise a patruen.
Actually, the way they work goes a little something like this:
(Someone can correct me if I'm wrong)
Step 1: You supply the "seed" value for the random number generator.
The Computer comes up with a second seed value.
Step 2: The two numbers are concatanated, and a chunk of bits is
"grabbed" from these. This value is returned to you as a random
number.
The number returned to you is also used as the next seed value.
Note that if you run the same seed value, you will always get the same
result. Therefore, if you are using a sequence of random values, it
is only necessary to know the seed value to generate all succeeding
numbers.
This is why cryptographers despise the idea of using computers to
generate the random values for their encryption.. (Its also why you
can buy CDs filled with truly random digits for encryption purposes)
Please also note that it has been demonstrated that for very large
iterations through the C++ random number generator, it turns out that
some patterns emerge, and the numbers don't tend to be very random
after all!
I would tell you that using a computer to generate your numbers would
be okay, if and only if you used a random methodology for generating
the *seed* value, and you generated a new random seed for each
successive random number.
Such a method could include adding up all character presses and mouse
movements on the PC for some amount of time, or perhaps the sum of the
bytes you transferred to and/or from your ISP for a certain period of
time. Perhaps the summation of the frequencies of various random
sounds around the house (ie leave your microphone on with the volume
up for some amount of time)
Personally, I think the last option would be optimal, especially if
you live in a big city where you can record random F-Us and cars going
by. <g>
Hope this helps!
[-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-]
John K. McDonald, Jr. Alcatel, USA
[EMAIL PROTECTED]
please remove -delete- for responses.
--
"I speak for me and not this company"
TO SPAMMERS:
Please view the definitions for
"telephone facsimile machine,"
"unsolicted advertisement," and the
prohibition and penalty for sending
unsolicited faxes before sending Un-
solicited Commercial E-mail to the
above address. Violators WILL BE
PROSECUTED. These can be found
in:
The Telephone Consumer Protection Act
of 1991, Title 47, Chapter 5,
Subchapter II, Section 227.
[=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=]
------------------------------
From: [EMAIL PROTECTED] (Michelle Davis)
Subject: Can you use HASH functions for identification?
Date: Wed, 28 Jul 1999 21:58:17 GMT
I just came up with a neat idea for use in identification. I wanted to
ask if anyone knew if this sort of thing is already around.
I'm thinking you could take your challenge text, coupled to a
reference number of some kind, and run that through something like
SHA-1. You send the message digest, together with an unencrypted
version of the reference number. Now, the entity that wants to
authenticate takes the secret challenge text, which it knows (If
multiple users are involved, I suppose it could come out of some
central seed to simplify key-management issues), adds the known
reference number to the end of it, and runs the whole thing through
SHA-1. If the result is the same as the MD sent by the party in
question, it's quite clear that that party knows the secret - the
challenge text - and so it can be securely identified.
Sure, this isn't as spiff as digital signatures, but it's still really
secure. If you think about it, say it takes a six-million-dollar
machine to find a SHA-1 collision in any reasonable time (I'm building
on Van Oorson and Wiener's article here - we're talking brute-force
searches), to get back to the challenge text, you're have to search
for something like 2^(p*n) collisions, where n is your MD length (160
bits in SHA-1) and p is the probability that you'll find the challenge
text sooner than after 2^n tries. If x is 50%, we're talking about
having to find 2^80 collisions. This means you'd need around 2^80 of
those $6,000,000 machines working in parrallel, which isn't really in
our universe. If anything, it's safer than 2048-bit RSA.
Anyone knows if this sort of thing is already around? Either way, does
my authentication scenario make sense? I'd really like to hear some
input.
Thanks,
Michelle
------------------------------
From: [EMAIL PROTECTED] (Gergo Barany)
Subject: Re: Prime numbers wanted
Date: 28 Jul 1999 22:24:06 GMT
In article <7nnnht$2n8$[EMAIL PROTECTED]>, Krunoslav Leljak wrote:
>: enough odd to be) prime (The Miller-Rabin test).
>
>: int My_Simple_Algorithm (int n)
>: {
>: int temp=n;
>
> // I would add this:
> if (temp % 2==0) temp++;
Not a bad idea. It might be faster, however, to use this:
temp+=1-temp%2;
>: while (!is_prime(temp)) temp+=2;
>: return(temp);
>: }
>
>... otherwise it may go to infinity ;)))
>
>Kruno.
>
--
The difference between art and science is that science is what we
understand well enough to explain to a computer. Art is everything else.
-- Donald Knuth, "Discover"
GU d- s:+ a--- C++>$ UL+++ P>++ L+++ E>++ W+ N++ o? K- w--- !O !M !V
PS+ PE+ Y+ PGP+ t* 5+ X- R>+ tv++ b+>+++ DI+ D+ G>++ e* h! !r !y+
------------------------------
From: [EMAIL PROTECTED] (John McDonald, Jr.)
Subject: Re: Prime numbers wanted
Date: Wed, 28 Jul 1999 21:36:42 GMT
On 28 Jul 1999 20:01:01 GMT, Krunoslav Leljak <[EMAIL PROTECTED]>
wrote:
>: enough odd to be) prime (The Miller-Rabin test).
>
>: int My_Simple_Algorithm (int n)
>: {
>: int temp=n;
>
> // I would add this:
> if (temp % 2==0) temp++;
>
>: while (!is_prime(temp)) temp+=2;
>: return(temp);
>: }
>
>... otherwise it may go to infinity ;)))
>
>Kruno.
>
Nice catch!
[-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-]
John K. McDonald, Jr. Alcatel, USA
[EMAIL PROTECTED]
please remove -delete- for responses.
--
"I speak for me and not this company"
TO SPAMMERS:
Please view the definitions for
"telephone facsimile machine,"
"unsolicted advertisement," and the
prohibition and penalty for sending
unsolicited faxes before sending Un-
solicited Commercial E-mail to the
above address. Violators WILL BE
PROSECUTED. These can be found
in:
The Telephone Consumer Protection Act
of 1991, Title 47, Chapter 5,
Subchapter II, Section 227.
[=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Prime numbers wanted
Date: Wed, 28 Jul 1999 22:37:00 GMT
Krunoslav Leljak <[EMAIL PROTECTED]> wrote, in part:
> // I would add this:
> if (temp % 2==0) temp++;
That is a clever way to detect integer overflow, but I think that was
pseudocode to illustrate a search for primes that, in fact, wouldn't
fit in a single integer, even a "long" one.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Mel Yorkian)
Subject: Re: With all the talk about random...
Date: Wed, 28 Jul 1999 23:04:17 GMT
"Jeffery Nelson" <[EMAIL PROTECTED]> wrote:
>What's so bad about C++ or (The dreader, but still valad) BASIC functions
>for generateing random numbers. Are their methods flawed? I know they
>derive them from a list and the time of day, but this seems random ENOUGH to
>not be able to recognise a patruen. I was useing random keys in MY one time
>pad generated by C++. Should I reconsider?
The real reason for the strictness you may encounter, concerning the way
random numbers must be generated, is that the mathematical proof of the
unbreakability of the OTP has absolute randomness of the pad as an
important condition. If you use a less-than-perfect method then your
encryption might still be unbreakable, but you won't be able to prove it.
--
"Mel Yorkian" better known as [EMAIL PROTECTED]
012 3456789 <- Use this key to decode my email address.
Fun & Free - http://www.5X5poker.com/
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: What is twofish ???
Date: 29 Jul 1999 01:10:40 GMT
you'll probably get a million responses, but this will probably answer
most of your questions.
http://www.counterpane.com/twofish.html
Developer is Bruce Schneier, author of Applied Cryptography.
Keith
spike ([EMAIL PROTECTED]) wrote:
: Hello again...
: What is twofish ? How does it compare in terms of speed and security
: to other popular encryption algorithms ? Is it opensource ? Who
: developed it ?
: Thanks in advance...
: Spike
------------------------------
From: [EMAIL PROTECTED] (Isaac)
Crossposted-To: talk.politics.crypto
Subject: Re: OTP export controlled?
Date: 29 Jul 1999 01:03:35 GMT
On Tue, 27 Jul 1999 02:55:24 GMT, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>/*
>Jerry Park wrote:
>> 'they' can call anything anything 'they' want. Governments often do
>> things like that.
[ C code snipped without comment]
I'm sure it's ~possible~ to assemble a crypto system out of exportable
components. Random number generators, routines which XOR files,
etc are probably each exportable.
But the real art is assembling these things into a usable system.
It's even more of an art to build a system that has the potential
for use by the greater part of the public. The software
needed to take a rudimentary implementation of the OTP and convert
it into a full blown, usable system are neither trivial, easily
assembled, or exportable as a single component. Software with crypto
shaped holes in it, that is with "hooks" for crypto is also not
exportable.
Isaac
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: What the hell is XOR?
Date: Thu, 29 Jul 1999 00:30:32 GMT
In article <7nish2$34oa$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> >"SCOTT19U.ZIP_GUY" wrote:
> >> XOR R1,R2 which is make r2 = r1 XOR r2
> >> XOR R2,R1 which is make r1 = r1 XOR r2
> >> XOR R1,R2 which is make r1 = r1 XOR r2
> >
> >This is a well-known hack. If it weren't so well known,
> >it would be obscure and thus require documentation via a
> >comment in the source code at that point. Unless there
> >is a bottleneck at that point, swapping via a temporary
> >would be clearer and thus preferable (from a code
> >maintenance point of view).
>
> Well the way you sugguest would be clearer to a
> programmer who does not know much. But the
> way I did it is faster and saves on stack space.
> But if you have the freedom and money to use
> time and memory as you like then go your way.
> The main problem with your way is that it is a
> dumbing down approach and when you have to
> program real time stuff like a missle intercept
> your brain becomes to fat to use methods that
> would be crucial. So it is better to use such
> methods most of the time so your fresh when
> you need them.
>
> David A. Scott
What if r1 == r2?
I don't think you want both registers set to zero.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: spike <[EMAIL PROTECTED]>
Subject: What is twofish ???
Date: Wed, 28 Jul 1999 18:05:35 -0700
Reply-To: [EMAIL PROTECTED]
Hello again...
What is twofish ? How does it compare in terms of speed and security
to other popular encryption algorithms ? Is it opensource ? Who
developed it ?
Thanks in advance...
Spike
------------------------------
From: [EMAIL PROTECTED] (Shktr00p1)
Subject: Thanks for the input on my OTP, what about this?
Date: 29 Jul 1999 01:39:05 GMT
I've really appreciated the info on holes in my OTP. Since looping a key or
adding a password onto a key is weak...I've considered this.
Using a virtual drive. All files being contained within on file such as used
in drivespace or stacker. Here's my idea.
Using a one time pad on a virtual drive. Limiting it to a specific size. Say
no more than 50 megs(example), then using a 50meg OTP key off a CD-Rom?
OR
Using a very large key, say an entire 650meg key on a CD. Then when encrypting
files, each file never uses the same section of the key?
In comparison,
I've seen some examples of other code and I am left to doubt their strength as
well, for these reasons; You can use whatever algortyhm you choose. However,
no matter how fancy the mathmatics or shifting is, it only takes some reverse
engineering of the algorythm to leave these encrpytion systems bare. Once the
algorythm is reversed, you're only left with a short 128b OTP. I could go and
expand, shift, and convert data types too. Yet all you'd have to do is reverse
the algorythm. I've come up with an algorythm using these tactics.
Here's my example.
Check short 128bit key, base the algortyhm on that. (using
shifting,expanding,ect.)
if the first byte of the key is say "�" turn , turn the file byte value into
its ascii value, say 170, turn that into a string "170" and encrypt the string
one character at a time. Turning one bytes into 3.
If the second byte of the key is say "�", turn the byte into a value, swap the
characters around and then encrypt each character. Turning one byte into 3
again.
For others just encrypt, others swap bytes before or after....ect.
Creating an entire map of conditions, encrypt this way. Now all a good cracker
has to do is dissasemble and reverse engineer. Afterwards, crack it as a
128bit looped key.
These complex algorythms don't seem to be any better. Is there a valid reason
why they are? I'm not trying to be insulting. I really would like to know and
learn.
( ( (( Shock Troop )) ) )
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: the defintion of Entropy
Date: 29 Jul 1999 01:13:23 GMT
If that was an intuitive approach, I'd hate to see a non-intuitive approach.
Keith
Anton Stiglic ([EMAIL PROTECTED]) wrote:
: I have seen some bad usage of the word entropy, so I taught I'd post the
: definition.
: There is two ways of considering entropy, one is mathematical (through a
: set of axioms), the other is intuitive, I present the last one here:
: Consider a source S that spits out bits, S -> 1 0 0 1 0 1 0 1 1
: One intersting problem is to caracterize the output.
: Say that the probability of outputs are p_0 = Pr(0) and p_1 = Pr(1).
: We would like to know the uncertinty about the output of the source
: S, that is, the entropy of S.
: The entropy of S can be considered as "the average lenght, in bits,
: needed to represent the output (a bit) of S".
: In other words, if S spits outputs with probability p_0, p_1, then
: the entropy of S (H(S)) is
: H(S) = H(p_0, p_1) = p_0 *lg_2 (1/p_0) + p_1*lg_2(1/p_1)
: Entropy can be generalized to a source that spits out elements of
: a different base. Say S spits outputs with prob p_0, p_1, p_2, ...,
: p_n,
: then the entropy of S is
: H(S) = H(p_0, p_1, ..., p_n) = sum(i=1; i<=n; i++) p_i*lg_2(1/p_i)
: numbered examples:
: S_0 -> 0000000... (S_0 outputs a constant)
: then p_0 = 1 and p_1 = 0 and we have H(S_0) = 0;
: S_ur -> 10010110 (S_ur outputs a bit choosen uniformatly randomly
: then p_0 = 1/2 and p_1 = 1/2 and we have H(S_ur) = 1;
: Anton.
------------------------------
** 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
******************************
