Cryptography-Digest Digest #497, Volume #11 Wed, 5 Apr 00 21:13:02 EDT
Contents:
Re: GSM A5/1 Encryption (Matt Linder)
Re: Q: Entropy (Johann Hibschman)
Re: GSM A5/1 Encryption (David A. Wagner)
design of MD family ciphers (Amit Jain)
Re: Keeping numbers small in RSA (Bryan Olson)
Re: RNG based on Blum Blum Shub (Tom St Denis)
Re: generator of Zp (Tom St Denis)
Re: time-lock crypto (Tom St Denis)
Re: Can anyone decrypt this? ("Bruce Adler")
[Q] Knuth on ACGs in 3rd edition ("David C. Oshel")
Re: Is this code crackable? ("Jethro")
Re: RNG based on Blum Blum Shub (Bryan Olson)
Re: RNG based on Blum Blum Shub (Tom St Denis)
Re: Public|Private key cryptography? (Tom St Denis)
Re: [Q] Knuth on ACGs in 3rd edition (Tom St Denis)
Re: RNG based on primitive multiplicative generator. (Tom St Denis)
Re: RNG based on primitive multiplicative generator. (Tom St Denis)
Re: TEA? (Tom St Denis)
Re: Implementation of Blowfish (Tom St Denis)
Re: Implementation of Blowfish (Tom St Denis)
Re: generator of Zp (Gregory G Rose)
Re: RNG based on primitive multiplicative generator. (David A. Wagner)
Re: Q: Simulation of quantum computing (Bill Unruh)
----------------------------------------------------------------------------
From: Matt Linder <[EMAIL PROTECTED]>
Subject: Re: GSM A5/1 Encryption
Date: Wed, 05 Apr 2000 20:02:37 GMT
In article <8cfvb9$cqm$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> By modern cryptographic standards, A5/1 is a weak cipher, but I
> think you were more interested in the practicalities of interception,
> right?
>
Right.
>
> What's your threat model? The curious average man on the street
> who wanders down to Radio Shack to pick up a scanner, or a dedicated
> knowleadgeable individual with some budget (e.g., $10k), or worse?
>
> I think the GSM A5/1 cipher is likely to be secure against the former,
> but it would be unwise to assume that it is secure against dedicated
> attack by knowleadgeable individuals. Today, breaking GSM A5/1
appears
> to be feasible for corporate espionage, but probably not for most
curious
> hobbyists. But that could well change 3--5 years down the road; in
> this field, history teaches us that sophisticated attacks often have
> a way of filtering down to the street in the form of black boxes that
> require little or no sophistication to use.
>
You hit it on the head. My impression is that for protecting the
average soccer mom from having her kids soccer schedule listed in on by
some guy with a scanner, A5 is probably sufficent (for now). As for
knowleadgeable individuals, well thats another story.
> If you are interested in intelligence agencies, I would be amazed if
> they do not have the capability to eavesdrop on GSM traffic when they
> want to.
>
Perhaps I am naive, but I have not been overly inpressed by the three
letter guys. Mabey that's the way they want it.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Johann Hibschman <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: 05 Apr 2000 13:20:33 -0700
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen writes:
> Sorry that I didn't carefully read your follow-up. But it seems
> to be disputable why you do lumping based on the number of 1's (or
> equivalently 0's). The special sequence 01010101....... has a
> very regular pattern, while anothers with the same number of 1's
> may not. I am not sure that disregarding such properties wouldn't
> mean neglecting some essential crypto-relavant aspects.
Pattern? I care not for pattern. Or at least entropy doesn't, a
priori. ;-)
> One way that I could think of (though practically not realizable)
> is to take the Kolmogorov complexity to measure the information
> content instead of the entropy or other concepts that could be
> traced back to Shannon. But I don't know whether this is o.k. from
> the standpoint of crypto.
>From the little bit I know of it, Kolmogorov complexity is closer to
what you're asking for, not entropy. The Kolmogorov complexity will
give you a measure of the regularity of a given bit-string, while the
concept of entropy only applies to *ensembles* of bit strings.
You can define the entropy involved in rolling a 7 on 3 dice. But you
can't define the entropy of rolling 1 2 4 in an meaningful way.
Similarly, you could define the Kolmogorov complexity of the sequence
1 2 4, but you can't define the complexity of rolling a 7.
In short, the question you're asking (i.e. what's the entropy of a
given string) just doesn't make any sense.
--Johann
--
Johann Hibschman [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GSM A5/1 Encryption
Date: 5 Apr 2000 13:01:00 -0700
In article <8cg64i$kgc$[EMAIL PROTECTED]>,
> My impression is that for protecting the
> average soccer mom from having her kids soccer schedule listed in on by
> some guy with a scanner, A5 is probably sufficent (for now).
Right. And GSM is certainly far better than using an analog cellphone.
(That's saying something about analog cellphones, to be sure, but it is
important not to forget this.)
------------------------------
From: Amit Jain <[EMAIL PROTECTED]>
Subject: design of MD family ciphers
Date: Wed, 5 Apr 2000 19:41:11 GMT
Few basic doubts about Message Digest family hash functions.
Why is the Message Digest family designed the way it is ? Can attack on MD
be reduced to any hard problem ? If not then, on what is its security
based ?
I read in a book that it is based on Fiestal permutations. If this is
true, then why was Feistal permutation selected for its design ?
Amit Jain
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Keeping numbers small in RSA
Date: Wed, 05 Apr 2000 21:17:17 GMT
Rick wrote:
> I am having some trouble calculating result = A*B mod n as
> part of a modular exponentiation. The tempory value for
> A*B gets too big too store before the modular reduction.
> I am limited to 32 bit storage for the tempory register.
> Can anybody suggest a technique(s) or algorithm to reduce
> these numbers, ideally to allow large A and B usage.
Of course 32-bit integers are much too small for
secure RSA.
But for demo purposes, the mult_mod function below
will work on 32-bit unsigned integers. None of the
computations will overflow.
--Bryan
--
email: bolson at certicom dot com
#include <stdio.h>
#include <limits.h>
/*
* Call with a and b less than m.
* Returns a * b mod m.
*/
unsigned long mult_mod(unsigned long a,
unsigned long b,
unsigned long m)
{
unsigned long result = 0;
unsigned long bit = ULONG_MAX - (ULONG_MAX >> 1);
/* Highest bit set, all others zero. */
while (bit)
{
if (m - result > result)
result = result + result;
else
result = result - (m - result);
if (b & bit)
{
if (m - result > a)
result = result + a;
else
result = result - (m - a);
}
bit = bit >> 1;
}
return result;
}
/*
* Call with b and e less than m.
* Returns b to the e mod m.
*/
unsigned long exp_mod(unsigned long b,
unsigned long e,
unsigned long m)
{
unsigned long result = 1;
unsigned long bit = ULONG_MAX - (ULONG_MAX >> 1);
/* Highest bit set, all others zero. */
while (bit)
{
result = mult_mod(result, result, m);
if (e & bit)
result = mult_mod(result, b, m);
bit = bit >> 1;
}
return result;
}
int main()
{
unsigned long prime = 3000000019UL;
unsigned long base = 3000000001UL;
printf("These should be the same: %lu, %lu\n",
base, exp_mod(base, prime, prime));
return 0;
}
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RNG based on Blum Blum Shub
Date: Wed, 05 Apr 2000 22:15:32 GMT
Mok-Kong Shen wrote:
> While my humble knowledge by far doesn't suffice to evaluate
> the strength of your scheme, I do like to suggest that you
> begin by studying the statistical properties of the bit stream
> obtained. A crypto PRNG need not have extremely superb
> statistical qualities that are demanded in computer simulation
> studies but shouldn't on the other hand be fairly poor
> statistically. Should it turn out that the bit streams fail,
> for example, the FIPS 140-1 tests, then you could save your
> effort to prove the strength in the first place. (Of course,
> I wish that you would have success with your scheme.) Like with
> the BBS, special attention should be paid to liability to short
> cycle lengths, I suppose.
Well the plus side, the period is known to be at most p-1, since a
primitive generator mod p will make all elements mod p at some point.
By only giving out 8 bits of a [say] 512 bit number [with a 513 bit
prime] you will most likely not get most of the result. And since the
generator is dense [that is it's over (p-1)/2, and has at least
log2(p)/2 bits set] we know the state will be throughouly [sp?] mixed in
step.
However the lsb's could have significant poor statistical properties
[which is why I will try it tonight], or you could learn enough of the
state by the the log2(p) lsbs.. etc.
Any comments or thoughts are certainly welcomed.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: generator of Zp
Date: Wed, 05 Apr 2000 22:21:04 GMT
Bob Silverman wrote:
>
> In article <[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> <snip>
>
> > If your prime is p- strong, just randomly try 'g' values to get
> >
> > g^p-1 = 1 (mod p)
> > g^(p-1)/2 != 1 (mod p)
> >
> > Any 'g' that satisfies those too conditions is a generator mod p.
> ^^^
> If you want your replies to be professional, may I suggest that you
> proofread your posts?
Sorry. I am kinda busy. I am trying to give out my amateur *free* help
when I can.
> And your reply is wrong. (Hint: there is a value of g
> such that g^(p-1) = 1 mod p, and g^q = -1 mod p).
The case of g = -1 right? I would think we assume 2 < g < p - 1 ?
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: time-lock crypto
Date: Wed, 05 Apr 2000 22:22:32 GMT
"David A. Wagner" wrote:
>
> The attack is trivially parallelizable, so it's not time-lock.
>
> The adversary can throw hundreds of machines at the problem
> and solve it hundreds of times faster. Since the number of
> machines is under the control of the adversary -- not the
> time-lock puzzle designer -- it is the adversary who will have
> control on how long he has to wait before he can decrypt it.
>
> If this is ok, then you don't need to use factoring; there
> are far simpler constructions. But for most applications,
> this is not ok.
In one my self-replies I explain how I broke it.
tom
------------------------------
From: "Bruce Adler" <[EMAIL PROTECTED]>
Subject: Re: Can anyone decrypt this?
Date: Wed, 05 Apr 2000 22:55:40 GMT
"John Stone" <[EMAIL PROTECTED]> wrote in message
news:8cberg$sks$[EMAIL PROTECTED]...
> I bet you think this is pitiful, but I still can't figure it out. Any help
> would be greatly appreciated.
>
There's a "w" somewhere in the plaintext.
------------------------------
From: "David C. Oshel" <[EMAIL PROTECTED]>
Crossposted-To: alt.sources.crypto
Subject: [Q] Knuth on ACGs in 3rd edition
Date: Wed, 05 Apr 2000 18:11:51 -0500
I've heard that Don Knuth reports recent (post-1990) deprecations on the entire class
of additive
congruential generators in his 3rd edition of _Art of Computer Programming_.
Does anyone know what the test is that he refers to, other than that
it's allegedly "simple"? Does anyone have source code?
A pity, if true, because Mitchell & Moore's version has always looked like a
winner to me.
--
David C. Oshel mailto:[EMAIL PROTECTED]
Cedar Rapids, Iowa http://pobox.com/~dcoshel
``Tension, apprehension, and dissension have begun!" - Duffy Wyg&, in Alfred
Bester's _The Demolished Man_
------------------------------
From: "Jethro" <[EMAIL PROTECTED]>
Subject: Re: Is this code crackable?
Date: Wed, 5 Apr 2000 17:15:21 +0100
1198 wrote in message <[EMAIL PROTECTED]>...
>If the key file can be safely sent to the other end without security
problem
>then there is no point of having any encrytion at all..
I understand that.
My intent (and I'm just playing around) was to physically hand the "PAD"
(I've learned something already) on a floppy to my recipient, whom I see
about every 6 months. The decrpyt program is also on the floppy. He can
work completely off the floppy, keeping everything off his HD. The decrpyt
program kills the encrpted file upon decryption.
I email him an encrypted file perhaps once a week, he moves it to his floppy
and decrypts. So he ends up with nothing on his HD (or, at the most the
encrypted files) and on his floppy only the decrpyt program, the decrypted
file(s) and the PAD.
Everyone is saying you can only use the PAD one time, hence the name "One
Time PAD". Is this simply because I cannot trust my recipient to follow my
instructions?
If he were to follow my instructions, how would the code be breakable? The
only email traffic would be the encrypted files. And if nothing but the
encrypted files are on his HD, nobody could snoop his HD when he is on-line
to find the PAD or any decrypted files to figure the PAD out.
>
>
>
>Jethro wrote in message <5owG4.81349$[EMAIL PROTECTED]>...
>>I'm new to this subject, but I'd appreciate an experts opinion on this.
>>
>>I've written a program that generates a "key" file. The key file is a
text
>>file composed of 10,000 randomly-selected ASCII characters (character
codes
>>1 through 126, excluding the end of file character code 026). The
>>characters were generated randomly using the CPU timer, mouse position and
>>current ocean water temp and barometric pressure inputs for randomizer
>>seeding.
>>
>>To encrypt a plain text file (of less than 10,000 characters, ASCII codes
1
>>through 126), the ASCII value of each character of the text file is added
>to
>>the ASCII value of each character of the key file. This summed character
>is
>>then placed into the encrypted file. Therefore, the encrypted file
>consists
>>of the same number of characters as the unencrypted file and all the
>>encrypted characters are ASCII character codes 127 through 256.
>>
>>To decrypt the encrypted file, the same key file is used, this time
>>subtracting the key character from the encrypted character to obtain the
>>ASCII value of the original text file.
>>
>>It works, but of course it requires one to physically give the key file to
>>someone else. My question is, is it possible to crack this type of code
>>without having the key file? I can't think of a way. Is this a
well-known
>>technique?
>>
>>
>>
>
>
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: RNG based on Blum Blum Shub
Date: Thu, 06 Apr 2000 00:13:12 GMT
Tom St Denis wrote:
> Well the plus side, the period is known to be at most p-1, since a
> primitive generator mod p will make all elements mod p at some point.
I don't see why knowing the period is at most something
would be on the plus side. The period is not known to
be at most p-1 nor at least p-1. Try 19*23 with seeds
10 and 20.
The generator argument doesn't work because we're dealing
with g^2, g^4, g^8,... and not g^1, g^2, g^3,...
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RNG based on Blum Blum Shub
Date: Thu, 06 Apr 2000 00:25:36 GMT
Bryan Olson wrote:
>
> Tom St Denis wrote:
> > Well the plus side, the period is known to be at most p-1, since a
> > primitive generator mod p will make all elements mod p at some point.
>
> I don't see why knowing the period is at most something
> would be on the plus side. The period is not known to
> be at most p-1 nor at least p-1. Try 19*23 with seeds
> 10 and 20.
Well I said in the description that you have to find a 'g' which is
primitive. If you find this, you can multiply anything in GF(p) and get
another unique element, upto p-1 times.
> The generator argument doesn't work because we're dealing
> with g^2, g^4, g^8,... and not g^1, g^2, g^3,...
Um, no. If we start with 'x' as our seed we are deeling with
M[0] = x
M[1] = gx
M[2] = gxx = gx^2
M[3] = gxxx = gx^3
(Where the output is the lower log2(p) bits of M[], and this is all mod
p of course).
Sorry about calling it based on BBS, it really is not.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Public|Private key cryptography?
Date: Thu, 06 Apr 2000 00:26:44 GMT
This is complete rubish. Factoring numbers 1024+ bits is not possible.
So your 'statistics' are moot.
Tom
[EMAIL PROTECTED] wrote:
>
> ###
> Simon Johnson wrote:
> > Every algorithm i have seen so far requires the use of massive numbers to be
> > secure. Are there any algorithm of this type that deal in small number?
>
> yes, ECC - Elyptic Curves
>
> Comparison from
> http://www.users.globalnet.co.uk/~firstcut/pgpfaq.html
> ----------------------
> Block RSA EC
> Cipher Key Key
> Length Length Length
> ----------------------
> 80 1024 160
> 112 2048 224
> 128 3072 256
> 192 7680 384
> 256 15360 512
>
> and from
> http://www.Certicom.com/ecc/wecc4.htm
> -------------------------------
> Time to RSA/DSA ECC RSA/ECC
> break key key key size
> in size size ratio
> MIPS
> years
> -------------------------------
> 10^4 512 106 5 : 1
> 10^8 768 132 6 : 1
> 10^11 1,024 160 7 : 1
> 10^20 2,048 210 10 : 1
> 10^78 21,000 600 35 : 1
>
> there is even program that uses it: Pegwit
> get it from: http://ds.dial.pipex.com/george.barwood/
> and windows version from: http://disastry.dhs.org/pegwit
>
> == <EOF> ==
> Disastry http://i.am/disastry/
> remove .NOSPAM.NET for email reply
> ### end pegwit v8 signed text
> b88d25bcb58d268e69265cf5a53bd34651fdf32f45e327a12a327543e2b2
> 6169395ea2de5f639cf8d1dd1951b289515051cf67176b0ff0a610444ff9
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: alt.sources.crypto
Subject: Re: [Q] Knuth on ACGs in 3rd edition
Date: Thu, 06 Apr 2000 00:28:38 GMT
"David C. Oshel" wrote:
>
> I've heard that Don Knuth reports recent (post-1990) deprecations on the entire
>class of additive
> congruential generators in his 3rd edition of _Art of Computer Programming_.
>
> Does anyone know what the test is that he refers to, other than that
> it's allegedly "simple"? Does anyone have source code?
>
> A pity, if true, because Mitchell & Moore's version has always looked like a
> winner to me.
Maybe he refers to the GAP test, or the fact they are linear. Generally
though a lfg with a big enough lag is sufficiently random [not secure,
but statistically well balanced].
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RNG based on primitive multiplicative generator.
Date: Thu, 06 Apr 2000 00:32:45 GMT
Mike Rosing wrote:
>
> Tom St Denis wrote:
> > Ouch... sorry I meant to inrepret the integer as a long vector of bits,
> > then to the dot product, so 5 <dot> 3 would be
> >
> > (1, 0, 1) <dot> (0, 1, 1) = 1*0 xor 0*1 xor 1*1 = 1
>
> So N[i] = {g^(x+i) mod p} dot b. If we map the integers into a normal
> basis,
> your dot operation is Trace(a+b). My gut reaction is that this is too
> linear,
> but I'm not going to try to prove it :-)
>
> How about Trace(b*g^(x+i) mod p)? That gives you 2 keys, x and b. All
> b does
> in this case is change x to x' as a single key, so it's probably not
> useful.
'b' wouldn't be to usefull. I would keep it as Trace(g^(x+i) mod p),
but that's my original idea.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RNG based on primitive multiplicative generator.
Date: Thu, 06 Apr 2000 00:33:56 GMT
"David A. Wagner" wrote:
>
> In article <Y6RE4.95936$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > How would one start to attack a generator like so:
> > [ M[i] = g*M[i-1] mod p; N[i] = M[i] dot-product b ]
>
> You might look at the papers which cryptanalyze truncated
> linear congruential generators. (M[i] = g*M[i-1]+a;
> N[i] = some bits of M[i]) The similarities are striking.
Where can I find these papers? Also note I say it outputs one bit at a
time, not several. However I am testing an idea which outputs the 8
lsbs.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: TEA?
Date: Thu, 06 Apr 2000 00:35:21 GMT
Simon Johnson wrote:
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >
> >
> > Simon Johnson wrote:
> > >
> > > Would a modified version of TEA, using a 16-bit block, and 32-bit key,be
> > > proportionally as strong as its 64-bit block, 128-bit key counterpart?
> > >
> > > Secondly, Is the addition mod 2^32 in TEA?
> >
> > Well no, cuz a 32 bit key is 2^96 times easier to solve, so it's not
> > proportional based on size [well it's exponential]. And it would be
> > easy to attack such a variant.
> >
> > And yes the addition is taken modulo 2^32.
> >
> > Tom
>
> Thanxs, I let me rephrase my question. Does the linar & differenential
> cryptoanayalsis strength remain the same if this modified version?
>
> Background: I'm going to use RC4 to generate a stream- key, and then use TEA
> as the main block-cipher. I'm betting on the fact the each pair of
> characters, in my proposed weaking, would have to be brute-forced to recover
> the text.
That's a bad idea. For every 2 bytes, I just have to try 2^31 keys
[avg] to find the bytes. So that means for a 100 byte message, I just
have to try 100 * 2^31 ~ 2^38 keys. That's about a day or two [or
three] work at the most.
I would keep TEA at it's full 64 bit block size, and 128 bit key.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Implementation of Blowfish
Date: Thu, 06 Apr 2000 00:37:43 GMT
No what I am going todo, is change all the ciphers to use the standard
IMACIPHER_ENCRYPT(unsigned char *input, unsigned char *output);
Interface. But in the mean time it should work fine on 32-bit
platforms. Sorry about that.
Tom
Bryan Olson wrote:
>
> Tom St Denis wrote:
> > I heard CB is a cool Crypto API, it includes Blowfish among it's other
> > symmetric ciphers.
>
> Hmmm, I suggest waiting until it's better tested.
>
> In ciphers.c we find:
>
> extern
> void blowfish_ENCRYPT(const unsigned char *plaintext,
> unsigned char *ciphertext);
>
> That declaration is contradicted by the implementation
> in BLOWFISH.C, which has the type:
>
> void blowfish_ENCRYPT(unsigned long *block,
> unsigned long *out)
> { ...
>
> It looks like it will behave differently on big-endian
> than on little endian machines, and differently on C/C++
> implementations where unsigned long is 32 bits than on
> those in which it is longer than 32 bits.
>
> You might pull my old Blowfish code out of the Python
> Cryptography Toolkit. (I don't know of any surviving
> Usenet archive that goes back far enough to have my
> originally posted version, and that only included the
> block functions, so it doesn't handle variable length
> strings as requested.)
>
> --Bryan
> --
> email: bolson at certicom dot com
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Implementation of Blowfish
Date: Thu, 06 Apr 2000 00:39:20 GMT
James Felling wrote:
>
> Tom St Denis wrote:
>
> > lordcow77 wrote:
> > >
> > > This is intellectually dishonest, implying an unbiased
> > > observation or judgement when in fact, CB is your own API. While
> > > I am fairly certain that you have no underhanded motives, fully
> > > disclosing your relationship to a product that you suggest to
> > > others is a standard ethical practice.
> >
> > I was trying to be funny and informative. If you find any problems with
> > CB though [which I am not doubting] please let me know.
> >
> > Tom
>
> There are no known problems with it that I have noticed ( I have given it a
> casual once over), but I do agree that it is best to say
>
> " I wrote the CB API and it is a good one go ahead and use it" vs. " I would
> recomend the CB API"
>
> The reasons behind this are
>
> 1) It prevents you from sounding like the individuals (who shall remain
> unnamed here) who plug their own unique crypto prducts as the best thing
> since sliced bread.
No I openly admit it needs work. And I am working on it daily :-)
> 2) Its your API be proud of it.
I am. It's taken quite a while to get all the functions in their.
> 3) It prevents people from thinking hey the guy who recomended this to me
> wrote it, and didn't say so at the time -- is there some weakness or the
> like to this or a backdoor that he could use. Firmly associating yourself
> with your product upfront prevents the apearance of having something to
> hide.( I know it is ridiculous, but that is the way it seems to work
> now-a-days)
Well none of the stuff in their is revolutionarly new or my-own.
However I have alot of portability issues to deal with. It's currently
only useable on 32-bit platforms, and not endianess interoperable.
Tom
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: generator of Zp
Date: 5 Apr 2000 17:40:41 -0700
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>If your prime is p- strong, just randomly try 'g' values to get
>
>g^p-1 = 1 (mod p)
>g^(p-1)/2 != 1 (mod p)
>
>Any 'g' that satisfies those too conditions is a generator mod p.
Not strictly true. There is also one element which
has a period of 2, which must also be avoided. As
it happens, that's easy, because it is -1 (or
"p-1" if you want to think of it that way).
>> 2) supposedly, the order of generator is (p-1) - is it always true?
That's what makes it a generator... it goes
through all the possible values on it's way back
to 1.
>> so that a^(p-1) mod p = 1.
>> but why a^q = -1 = p-1 (mod p) ?
Because halfway through the sequence (see below)
you must have hit the other square root of 1. But
this is an automatic consequence, not a condition.
Note that (-1)^q == -1, but -1 still isn't a
generator.
>Yes the period for a multiplicative generator mod a prime 'p' is always
>'p - 1'. I dunno about the a^q, except that if a is a generator a^q
>should never be 1 (mod p).
If the sequence {1, a, a^2, a^3, ..., 1, a, ...}
repeats after p-1 terms, a is a generator. The
sequence must repeat, and (by Fermat's little
theorem) the period must divide p-1, so it must be
either p-1, q, or 2. (Or one, if a == 0, but that
doesn't count.)
This stuff is very pretty once you get it clear in
your head.
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: RNG based on primitive multiplicative generator.
Date: 5 Apr 2000 17:05:45 -0700
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> "David A. Wagner" wrote:
> > You might look at the papers which cryptanalyze truncated
> > linear congruential generators. (M[i] = g*M[i-1]+a;
> > N[i] = some bits of M[i]) The similarities are striking.
>
> Where can I find these papers?
Your favorite research library?
If you have a university nearby, it's a good bet,
as always, with the cryptographic literature.
Search for, well, cryptanalysis of linear congruential generators,
and/or lattice reduction in cryptanalysis.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Q: Simulation of quantum computing
Date: 6 Apr 2000 00:51:08 GMT
In <[EMAIL PROTECTED]> Mok-Kong Shen <[EMAIL PROTECTED]> writes:
>Some questions of ignorance:
>Can one simulate a quantum computer with a common digital computer?
Yes.
>If yes, how to do that? Would that follow that one can obtain with
>software alone the uncertainty inherent in quantum theory and hence
>be able to get truly random bits that way?
No.
>If no, does that imply that a Turing machine can't simulate a
>quantum computer and hence that the latter is more powerful?
A Turing machine with a random oracle can completely ( though slowly) simulate a
quantum computer., incliding
the readout. If you do not care about the readout you do not need the random
number generator-- ie the classical computer can also tell you what the probabilities
of
various outputs are, something a quantum computer "does not do". (Of course a
classical computer can be
simulated with a quantum computer as well.)
>Thanks.
>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
******************************
