Cryptography-Digest Digest #75, Volume #12 Wed, 21 Jun 00 01:13:00 EDT
Contents:
Re: mother PRNG - input requested ("Joseph Ashwood")
Re: mother PRNG - input requested ("David S. Hansen")
Re: small subgroups in Blum Blum Shub (Bryan Olson)
Re: Weight of Digital Signatures (John Savard)
Re: Cipher design a fading field? (John Savard)
Re: Linear Feedback Shift Register *with* lock-up? ("bubba")
Re: DVD encryption secure? -- any FAQ on it (David A. Wagner)
Re: small subgroups in Blum Blum Shub (d g)
(June 20, 2000) Cipher Contest ("Adam Durana")
Re: Is this a HOAX or RSA is REALLY broken?!? ("Trevor L. Jackson, III")
Re: "What 'flagrant' bugging abuse?",asks Home Secretary Straw [Was Re: RIP Bill 3rd
Reading in Parliament TODAY 8th May] (Dave Howe)
Re: Linear Feedback Shift Register *with* lock-up? ("Trevor L. Jackson, III")
Re: DVD encryption secure? -- any FAQ on it (Joaquim Southby)
Re: Linear Feedback Shift Register *with* lock-up? (Joaquim Southby)
Re: Homophones (JKingQM)
Re: How encryption works ("Joseph Ashwood")
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: mother PRNG - input requested
Date: Tue, 20 Jun 2000 17:06:02 -0700
> If seed is only 32-bit and your messages aren't long, does having
> a PRNG period longer than 2^32 really gain anything?
Yes it does. It gains uncertainty. For example, if I have a pRNG with a
cycle of 12, 8-bit values, say it outputs:
0123456789AB
and another generator of cycle 6 with outputs
012345
and a message of length 5, from the first generator I have the possibility
of have the random values of
01234
12345
23456
34567
45678
56789
6789A
789AB
89AB0
9AB01
AB012
B0123
but with the second generator I have only
01234
12345
23450
34501
45012
50123
Giving me much better odds if I assume that a 5 exists in the list (5/6
versus 5/12). It's a very simple example, and there are certainly other
flaws, but it works for this example.
Joe
------------------------------
From: "David S. Hansen" <[EMAIL PROTECTED]>
Subject: Re: mother PRNG - input requested
Date: Wed, 21 Jun 2000 00:10:38 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
>
> If seed is only 32-bit and your messages aren't long, does
> having a PRNG period longer than 2^32 really gain anything?
Well, that's pretty much the source of my question. It seems
to me that it would be cryptographically insecure unless used
in applications that securely store the internal state of the
PRNG, and make use of it well beyond 2^32 times - which seems
to be a pretty tall order. That is why I ask my final
question: What prng's do you fine people find to be excellent?
=)
*** David S. Hansen
*** [EMAIL PROTECTED]
*** http://www.haploid.com
=====BEGIN PGP SIGNATURE=====
Version: PGP 6.5.3
iQA/AwUBOVAIMbUtlIUTAKGREQLAxgCfSdXu9KGpGID3BBxcKJ7NvMjkLqcAoPxb
4lEyOw1gSMyUqer9zpylmhHm
=FZqF
=====END PGP SIGNATURE=====
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 00:17:34 GMT
Mok-Kong Shen wrote:
> Counter-example: p=3, q=7, n=21. 7 is quadratic residue, since
> 7^2 = 49 = 7 mod n.
No it isn't - it's not in the multiplicative group mod n.
> However 7 has only 2 square roots: 7 and 14.
> (Bryan Olson's proof must also have a bug somewhere.)
I can't promise there are no mistakes in my presentation,
but that case is no counterexample.
The 'bug' in Mark's proof was that in that line he should
have said "x in Z_n*", not just "0 < x < n"; it's a trivial
typo-class mistake since he was clear in several other
places that the domain is the multiplicative group.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Weight of Digital Signatures
Date: Wed, 21 Jun 2000 00:23:53 GMT
On Mon, 19 Jun 2000 20:25:01 GMT, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>Greg wrote:
>> ... Kudos to all who have had any
>> hand in helping the government see the light (finally)...
>Unfortunately, that probably means that even when an insecure
>digital signature scheme is used, you cannot refuse personal
>responsibility when you're forced to use it anyway.
Someone who agrees with me! At least on one point about this
announcement not being entirely good news.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Cipher design a fading field?
Date: Wed, 21 Jun 2000 00:30:51 GMT
On Mon, 19 Jun 2000 20:20:46 GMT, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>"John A. Malley" wrote:
>> That immediately raises this question : Can we even encipher and cipher
>> plaintext strings of a Turing-unrecognized language?
>? Arbitrary bit strings can be enciphered and deciphered.
Quite right. But while he clearly asked the wrong question, it is
possible that he was thinking of a more interesting question.
Normally, while cryptanalysis is essentially impossible if the
plaintext is a totally random bit string (of course, uncertainty about
the plaintext can still be reduced for simple cryptosystems, and this
doesn't apply to public-key) the only "reason" for encrypting such a
bit string is to use it as a key later for encrypting something
*useful*, like English text.
So, while one can encipher arbitrary bit strings, in practice one
cannot usefully encipher _only_ arbitrary bit strings.
Thus, the question he (may have) *meant* to ask is: can one convey
useful information of a general sort (not counting, say, some types of
telemetry), which is complete in itself, not merely a cipher key for
transmitting a later message - in a language that can't be recognized
by a Turing machine.
If that could be done, one's communications would be resistant to a
certain category of cryptanalysis.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: "bubba" <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math
Subject: Re: Linear Feedback Shift Register *with* lock-up?
Date: Wed, 21 Jun 2000 00:37:38 GMT
The book "Shift Register Sequences" is back in print now.
http://shop.barnesandnoble.com/booksearch/isbnInquiry.asp?userid=1L52CNM1BQ&;
mscssid=S18WX4RX86S92PJS00A3HCP45E5U3GL4&srefer=&salesurl=Rshop.barnesandnob
le.com/booksearch/results.asp&isbn=0894120484
"Ponder" <[EMAIL PROTECTED]> wrote in message
news:8iocit$1ghu$[EMAIL PROTECTED]...
> I'm looking to use a Linear Feedback Shift Register to implement
> a counter with minimal resources (i.e. fewer gates and wires than
> an additive incrementor). I've seen quite a bit of cryptographic
> literature on how to use an N-bit LFSR to count through (2^N)-1
> values before repeating. There is one value (usually all 0's or
> all 1's) where the LFSR would be "stuck" at the same value as
> it counts.
>
> What I'm really looking for, though, is an LFSR that counts
> through 2^N values and then *does* get stuck in the last state.
> This way when I find it stuck, I would know that it counted through
> all the values since its initial state. There would be one
> "minimal" value for the initial state, that would cause it to
> count through all 2^N values before sticking; if I want to count
> fewer steps I would pick an initial value further along the
> sequence.
>
> Does anyone out there know how to do this? I've looked at some
> of the polynomial theory on LFSR's, but guess that it only
> applies to counters that actually loop through a sequence rather
> than iterating through a sequence and looping on a final value.
>
> Also, is there a good algorithm for converting the elements of
> an LFSR sequence into the actual value of the count? (Or more
> precisely, for mesuring the number of iterations between two
> values). For small N you could just count through the sequence
> until you find a match, but I'm interested in N around 32 or 64
> so this would take too long.
>
> Thanks in advance,
>
> Carl Ponder
> [EMAIL PROTECTED]
>
> --
>
> <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>
> Carl Ponder, Ph.D. Carl Ponder [EMAIL PROTECTED]
> AIX Performance Tools IBM Server Division Phone: (512) 838-1638
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: DVD encryption secure? -- any FAQ on it
Date: 20 Jun 2000 17:37:36 -0700
In article <8ip0hc$e8o$[EMAIL PROTECTED]>,
Wim Lewis <[EMAIL PROTECTED]> wrote:
> Ummmm? Surely playing a legally-acquired DVD on my legally-acquired
> computer in the legally-approved manner (no public performance or anything)
> counts as "use", not "copying". I'm even playing it in the DVDCCA-endorsed
> geographical region.
You'd think so, wouldn't you?
But don't count on it. At least in the US, there seem to be ongoing
legal disputes over exactly this type of issue.
Follow-ups to talk.politics.crypto, please. This is not a technical issue.
------------------------------
From: d g <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: 20 Jun 2000 18:08:39 -0700
> > OK. Let p, q be prime numbers, p = q = 3 (mod 4), and let n = p q.
> > Choose an integer x, 0 < x < n. Then y = x^2 (mod n) is a quadratic
> > residue, mod n.
This part is OK.
> > I claim (a) that y has four square roots, mod n, and (b) that exactly
> > one of these square roots is a quadratic residue.
There is a problem here.
>
> Counter-example: p=3, q=7, n=21. 7 is quadratic residue, since
> 7^2 = 49 = 7 mod n. However 7 has only 2 square roots: 7 and 14.
> (Bryan Olson's proof must also have a bug somewhere.)
Consider the structure of the ring of integers mod n - in particular,
if you look at the multiplicative group (Z/(n))*, it is isomorphic to:
(Z/(p))* X (Z/(q))*
that is, it is the cross product of two cyclic groups of sizes (p-1)
and (q-1) respectively.
If you consider the ring homomorphism f that takes a number mod n to a
tuple (a,b) of numbers mod p and q, this map is onto. The kernel of f
is the ideal (3*7).
If you choose random elements in the *multiplicative* cyclic subgroups
and square them, you get a quadratic residue with 4 roots as the
poster remarked.
However, if one of the choices is 0 (mod p) or (mod q), then you get
only two square roots. To wit:
7 = 1 mod 3
= 0 mod 7
If you take roots in the cyclic subgroups, you get (-1,0) and (1,0)
which map to 14 and 7 mod 21 respectively.
This is because 0 is not a member of the multiplicative group mod q -
that is, the residue 7 lies in the kernel of the homomorphism f.
There are (p-1) + (q-1) + 1 = p + q - 1 elements in the kernel. Out
of these, the kernel of f has ((p+q-2)/2) quadratic residues with 2
square roots each, and an equal number of quadratic nonresidues.
You will find that mod 21, there are four residues in f's kernel: (7,
9, 15, 18), which have two square roots each. The quadratic
nonresidues in f's kernel are (3, 6, 12, 14). Of course, if you came
upon any (nontrivial) element of the kernel of f, you could factor the
modulus by taking the gcd of the element and the modulus; that is,
there is an efficient reduction from finding a nontrivial element of
the kernel of the homomorphism f to factoring n.
==
Dipankar
[EMAIL PROTECTED]
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: (June 20, 2000) Cipher Contest
Date: Tue, 20 Jun 2000 20:34:56 -0400
I've updated the website. There are several new ciphers. My route to that
website just became pretty poor, so I did not get to complete all the
updates I wanted to. But I did get all the new ciphers into the listing.
All I really need to do is add the email addresses of the people who broke
LETSIEF2 and MMBOOZE. For those of you who don't know the URL its
http://www.wizard.net/~echo/crypto-contest.html
- Adam
------------------------------
Date: Tue, 20 Jun 2000 21:25:40 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Eric Smith wrote:
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
> > However, no system with the general conceptual ability of a normal
> > 10-year-old human has yet been demonstrated.
>
> Heck, I'd be impressed if they reached the conceptual ability of a
> 2-year-old. I suspect that the gap from the current state to the
> equivalent of a 2-year-old is *much* larger than the gap from the 2-year-old
> to adult.
Analogies with children are dangerous because children display their
intelligence by learning rather than by performing. An AI may exercise
judgement that was designed in (by picking the brains of human experts) without
having any capacity for refining those judgements. Such capability is often
referred to as an expert system. Learning and performing intelligently are
fundamentally distinct processes.
------------------------------
From: Dave Howe <DHowe@hawkswing>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: "What 'flagrant' bugging abuse?",asks Home Secretary Straw [Was Re: RIP
Bill 3rd Reading in Parliament TODAY 8th May]
Date: Wed, 21 Jun 2000 02:16:13 +0100
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[20 Jun 2000 11:01:38 GMT]),
[EMAIL PROTECTED] (U Sewell-Detritus) said :
>James Hammerton <[EMAIL PROTECTED]> wrote:
>
>>You have to prove you're not lying when you say that, which is well impossible.
>
>In Letters to the Editor, Jack Straw, the British Home Secretary
>poses the following question to the readers of The Daily Telegraph
>(Monday 19 June 2000):
>
>--------
>Unjustified worries about e-mails
>
>SIR - You peddle many erroneous assumptions about the
>Regulation of Investigatory Powers Bill, including the
>extraordinary assertion that there has been "flagrant"
>abuse of telephone interception.
>Where is the evidence for this?
Jack Straw has a... shall we say blinkered view of the world - he
belives that almost unlimited power can be vested in the officials of
the Police, Inland revenue, Health and safety executive and so on, but
no abuse will or can take place.
I pause to allow the scornful laughter to die down....
------------------------------
Date: Tue, 20 Jun 2000 21:34:36 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math
Subject: Re: Linear Feedback Shift Register *with* lock-up?
bubba wrote:
> The book "Shift Register Sequences" is back in print now.
>
> http://shop.barnesandnoble.com/booksearch/isbnInquiry.asp?userid=1L52CNM1BQ&;
> mscssid=S18WX4RX86S92PJS00A3HCP45E5U3GL4&srefer=&salesurl=Rshop.barnesandnob
> le.com/booksearch/results.asp&isbn=0894120484
The blurb on that page is a bit eclectic:
"bn.com customers who bought this book also bought:
Vittorio the Vampire: New Tales of the Vampires, Anne Rice
River's End, Nora Roberts,Fowler
Hannibal, Thomas Harris"
>
>
> "Ponder" <[EMAIL PROTECTED]> wrote in message
> news:8iocit$1ghu$[EMAIL PROTECTED]...
> > I'm looking to use a Linear Feedback Shift Register to implement
> > a counter with minimal resources (i.e. fewer gates and wires than
> > an additive incrementor). I've seen quite a bit of cryptographic
> > literature on how to use an N-bit LFSR to count through (2^N)-1
> > values before repeating. There is one value (usually all 0's or
> > all 1's) where the LFSR would be "stuck" at the same value as
> > it counts.
> >
> > What I'm really looking for, though, is an LFSR that counts
> > through 2^N values and then *does* get stuck in the last state.
> > This way when I find it stuck, I would know that it counted through
> > all the values since its initial state. There would be one
> > "minimal" value for the initial state, that would cause it to
> > count through all 2^N values before sticking; if I want to count
> > fewer steps I would pick an initial value further along the
> > sequence.
> >
> > Does anyone out there know how to do this? I've looked at some
> > of the polynomial theory on LFSR's, but guess that it only
> > applies to counters that actually loop through a sequence rather
> > than iterating through a sequence and looping on a final value.
> >
> > Also, is there a good algorithm for converting the elements of
> > an LFSR sequence into the actual value of the count? (Or more
> > precisely, for mesuring the number of iterations between two
> > values). For small N you could just count through the sequence
> > until you find a match, but I'm interested in N around 32 or 64
> > so this would take too long.
> >
> > Thanks in advance,
> >
> > Carl Ponder
> > [EMAIL PROTECTED]
> >
> > --
> >
> > <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>
> > Carl Ponder, Ph.D. Carl Ponder [EMAIL PROTECTED]
> > AIX Performance Tools IBM Server Division Phone: (512) 838-1638
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: DVD encryption secure? -- any FAQ on it
Date: 21 Jun 2000 02:18:22 GMT
In article <8ip0hc$e8o$[EMAIL PROTECTED]> Wim Lewis,
[EMAIL PROTECTED] writes:
>Ummmm? Surely playing a legally-acquired DVD on my legally-acquired
>computer in the legally-approved manner (no public performance or anything)
>counts as "use", not "copying". I'm even playing it in the DVDCCA-endorsed
>geographical region.
>
The MPAA might disagree with you if they could figure out what their own
opinion on the subject is. See
<http://www.theregister.co.uk/content/4/11397.html> for part of Valenti's
testimony on the DMCA and Fair Use. Caught with his hand in the cookie
jar.
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math
Subject: Re: Linear Feedback Shift Register *with* lock-up?
Date: 21 Jun 2000 02:25:23 GMT
In article <8iocit$1ghu$[EMAIL PROTECTED]> Ponder,
[EMAIL PROTECTED] writes:
>What I'm really looking for, though, is an LFSR that counts
>through 2^N values and then *does* get stuck in the last state.
>This way when I find it stuck, I would know that it counted through
>all the values since its initial state. There would be one
>"minimal" value for the initial state, that would cause it to
>count through all 2^N values before sticking; if I want to count
>fewer steps I would pick an initial value further along the
>sequence.
>
>Does anyone out there know how to do this? I've looked at some
>of the polynomial theory on LFSR's, but guess that it only
>applies to counters that actually loop through a sequence rather
>than iterating through a sequence and looping on a final value.
>
You could hardwire the "sticking" state into a comparator (along with the
internal state of the LFSR) to disable the LFSR clock. That would
probably up your gate count beyond what you want, though.
------------------------------
From: [EMAIL PROTECTED] (JKingQM)
Subject: Re: Homophones
Date: 21 Jun 2000 04:11:32 GMT
What do you mean by "fitting a HMM, or SVD of the transition matrix"? Can you
give me any references? Thanks.
John King
[EMAIL PROTECTED]
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: How encryption works
Date: Tue, 20 Jun 2000 21:52:22 -0700
Well, I'll give it a try, hope I help at least a little.
> 1) is n or e the public key?
Each is 1 part of the 2 part public key
> 2) if M=message, is this the checksum of the whole
message, of 1 character,
> blocks of characters, or what?
I read ahead some and it seems that you're asking about the
PGP case (instead of the original statement). In PGP the
value to be encrypted is actually the key to the secret key
cipher. It's done this way because a secret key cipher is
very much faster than the known public key ciphers.
> 3) the line with "d=....". When I did this out, (3^(-1))
mod ((4)(6)) didn't
> equal 16... I got 1/3.
That would normally be true, except that in modular
arithmetic consists of only the integers less than N, where
in your example N = 4*6 = 24. Given this and the other
statement of the values (and the more common/useful one) is:
de = 1 mod phi(n), specifically 3d = 1 mod 24
This can be restated as
3d = 1+24k
for some integer pair k,d.
Unfortunately this statement of the equation has no
solution, in fact with a public exponent of 3, a modulo of
35 has no solution. This is a rare situation, but be dealt
with by verifying that p-1 and q-1 are not divisible by e,
this shouldn't be a problem if you chose e to be at least as
large as p and q, while both 5 and 7 are 1 bit longer than
3, or you can just compute it.
>
> Other questions:
> I have pgp5.5. They key's properties said
Diffie-Hellman/DSS, with CAST cipher.
> What in the world does this mean? Isn't DH/DSS the
encryption, so why need CAST
> [or IDEA which I saw on other keys]?
Actually what happens in this case is that DH (actually a
varient called ElGamal ) is used to encrypt the key, because
CAST is several times faster (something like 100x), and is
considered more secure. DSS is actually used for signatures.
>
> I haven't read about any encryption methods that have
broken, which didn't use
> a brute force attack. Are there any and how did the
decryption work?
There are actually several. If you search the history of
this newsgroup you'll find a very large number of them.
>
> When I export my public key to people, which is a DH/DSS
CAST ciph. 2048/1024
> bit key, the key is in plaintext [like Hkel3jadAio3nDlLoWX
...]. 2048bit[or is
> it 1024?] / 8bit(per byte) = 256. but my key is > 256
bytes.
That's because there is more information contained in public
key than just the public values, it also includes
miscelaneous information about you (name, e-mail address,
preferred cipher, etc), and formatting.
>
> I don't plan to make some great encryption method and get
famous or anything, I
> just want to know how this works because I think it's very
interesting. I'm
> only 14, so bear with me...
No problem, I'm always here to help.
Joe
------------------------------
** 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
******************************
