Cryptography-Digest Digest #952, Volume #9 Thu, 29 Jul 99 23:13:03 EDT
Contents:
Re: Q: Does ElGamal require that (p-1)/2 is also prime like DH?
([EMAIL PROTECTED])
Re: DES permutations ([EMAIL PROTECTED])
Re: Modified Vigenere cipher ("Douglas A. Gwyn")
Re: How Big is a Byte? (was: New Encryption Product!)
Re: (Game) 80-digits Factoring Challenge (JPeschel)
Re: Prime numbers wanted ([EMAIL PROTECTED])
Re: Prime numbers wanted ("Douglas A. Gwyn")
Re: (Game) 80-digits Factoring Challenge ("Greg Keogh")
Re: (Game) 80-digits Factoring Challenge ("Dann Corbit")
Re: How Big is a Byte? (was: New Encryption Product!) (Paul Guertin)
Re: OK. Maybe I am missing something here. (John Wasser)
Re: (Game) 80-digits Factoring Challenge (Foghorn Leghorn)
Re: Encrypting in C++ and C ("Kwong Chan")
Re: cryptography tutorials (JPeschel)
Re: CSS/DVD Scrambler (Snusk-Pelle)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Q: Does ElGamal require that (p-1)/2 is also prime like DH?
Date: Thu, 29 Jul 1999 22:06:26 GMT
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> > I have to disagree. The following procedure
> > constructs p = 2q + 1 where p and q are prime
> > much faster.
> >
> > First, choose the range to search for p and q.
> > Sieve out small prime factors from both the p
> > range and q range. This way we only do further
> > tests when we know that neither p nor q will
> > have a small factor.
> >
>
> Of cours you can always test small numbers to make sure they
> don't divide p, this just adds to the algo naturaly, it only
> reduces it's complexity by a constant.
Actually no. We can let the number of small primes
we use increase with increasing q, so the improvement
is better than a constant factor. But that's a side
point to the main point below.
[...]
> > do one
> > iteration of a Fermat test on q with a base of 2.
> > If it passes, do a base-2 Fermat test on p.
> >
> > Finally, do the iterated Miller-Rabin tests on q
> > and p.
>
> Again, you are adding a side-test. If you start spitting
> out algos with to much details, you loose people. I feel
> it's better to give the general idea, BEEING ABLE TO EXPLAIN IT,
> then give references and leave the reader do the rest.
I don't think you followed; I did not just go into
more detail on how to test q and p. You had said to
start by finding a prime q and then test the primality
of p = 2q+1. That's slow, because you spend a long
time certifying candidate q values, only to throw them
away when 2q+1 fails a quick test. The smart way is
to _interleave_ the testing of q and 2q+1.
Bob Silverman pointed out that once you have a prime
q, we can test 2q+1 with certainty (provided we were
right about q), and the test takes only as long as
one iteration of the Fermat test. We'd still want
to use the interleaved testing technique, up to the
final certification of p.
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES permutations
Date: Thu, 29 Jul 1999 22:57:46 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> [EMAIL PROTECTED] wrote, in part:
>
> >What is a Fab?
>
> A "Fab" is a facility where microchips are fabricated. Since there are
> only a few plants where chips are designed, and since they represent a
> large commercial investment, they are subject to potential pressures.
>
> John Savard ( teneerf<- )
> http://www.ecn.ab.ca/~jsavard/crypto.htm
>
Oh. I see, but what potential pressures could they
be subject to? Do you intend to imply that the
encryption microchips made there would have some
sort of non-volatile memory installed that would
remember the key and disgorge it when appropriately
tickled?
but this leads to another question: what if you,
somehow, put together several different microchips
made in places that don't like each other: China,
Israel, US, France, etc.
I don't know exactly how that would work, but
perhaps someone has some ideas.
zapzing
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Modified Vigenere cipher
Date: Thu, 29 Jul 1999 19:45:45 GMT
John Savard wrote:
>> Oh, yes, a mixed-alphabet Vigenere is definitely soluble, since once
> you have determined (by the Kasiski method) the length of the keyword,
I repeat: Kasiski is not the most powerful way to determine the period.
The simplest technique of significant power is to compute the "average
column IC" for the ciphertext stacked at various widths; the actual
period and its harmonics usually stick out like a sore thumb.
> you still only have monalphabetics to solve. Without the standard
> sequence to line up, it is a bit harder, and only indirect symmetry of
> position is available, but it is not impossible.
Indeed, MilCryp (I think it was Part II) goes through the analysis of
a representative example.
Indirect symmetry of position is not hard to implement; I had a Fortran
66 version running in a 12Kword 16-bit minicomputer back in 1973.
> If one uses key progression or autokey, though, the methods given in
> Gaines for those ciphers do stop working. While such ciphers still
> aren't "unbreakable", one may need more than one message for solution,
> and the methods required are probably harder to find.
Different methods are used for ciphertext autokey (where almost the key
is known in advance!) versus plaintext autokey (where it isn't).
I seem to recall an exposition in the Friedman-only version of MilCryp,
probably Part IV (whichever volume treats aperiodic polyalphabetics).
Regular key progression can be treated by methods developed for rotor
machines, e.g. use of Friedman squares. There is an introduction to
this in NARA-II, as a poor-quality photoreproduction which I'm slowly
turning into a word-processor file. (It was also reproduced in the
NSATJ, but that specific version has not to my knowledge been released
to the public. I don't want to bug the Agency about it, because their
declassifiers already have more than enough work to do.)
------------------------------
From: <[EMAIL PROTECTED]>
Crossposted-To: alt.folklore.computers
Subject: Re: How Big is a Byte? (was: New Encryption Product!)
Date: Thu, 29 Jul 1999 19:27:41 -0400
On Thu, 29 Jul 1999, John Savard wrote:
> [EMAIL PROTECTED] wrote, in part:
> >John Savard wrote:
>
> >> And it is true that one begins counting with the first object, and if
> >> one has a first object, one has one object.
>
> >I disagree completely. If you are counting the sheep crossing the road,
> >and at some point in time I inquire as to the elapsed count you will
> >give me a natural not an ordinal number. If my query follows
> >immediately after the start of your count you have zero sheep not one.
> >So zero is the starting number.
>
> That kind of activity is a sort of counting. Normally, though, when
> one counts objects one moves towards a pool of passive objects, and
> begins counting by taking the first object in view or in hand.
>
> When one is counting events, then one must initialize to a zero state.
>
> >You may argue that you didn't "start counting" until the first sheep
> >arrived, but you were watching the road in the same state prior to the
> >first sheep as prior to the second sheep except for the value of your
> >"current count". So I maintain that you "started counting" when you
> >started watching for sheep, not when the first sheep arrived.
>
> >B. Kernigan identified this as the most important issue in programming
> >in an interview with Unix Magazine (Journal?) about 8 years ago.
>
> Despite the fact that Brian Kernighan is a well-respected programmer,
> and the co-author of several important books on C and Unix, I'm
> tempted to say, based on your statement, that I feel sorry for him if
> he thinks this is "the most important issue in programming".
>
> Zero may be my first counter state, but it is not the number
> associated with the first item or event. As there are times when
> reserving a storage location for element zero of an array makes sense,
> and other times when it does not, because of the purpose to which the
> array will be put, flexibility is useful...but, on the other hand,
> having to specify this every time is wasteful too. Starting with
> element zero at least allows both option with, at worst, a slight
> waste of storage, which is probably worth it to make one's program
> easy to understand and document, and avoid unnecessary offset
> arithmetic.
The problem with this is that array[0] is the first item. The reason this
is a problem is that in computer addressing the address refers to the next
item in memory (i.e. the item that starts at array[0]). When people count
they count with the current count pointing backwards toward the last
object counted. Also, we were taught to count as if the spaces
between the things was the actual number. Maybe an ascii graphic will help
illustrate:
|--------|--------|--------|--------|---------|--------|
^ ^^^ ^ ^^^ ^ ^^^ ^ ^^^ ^ ^^^ ^ ^^^ ^
0 1st 1 2nd 2 3rd 3 4th 4 5th 5 6th 6
| is the number and -------- is the thing.
Now the first thing is actually between 0 and 1. We just look at it
bacwards from the way a computer does. The first thing starts at 0 and
ends at 1. But we tend to think in terms of finite, indivisible objects.
Byte 0 (or 1) is actually the thing that starts at address 0 and ends at
address 1. It is neither address 0 or address 1 which is the way many
people tend to think about objects.
Going back to the discussion about Cribbage. Someone said that they have
troubles remembering to leave 7 holes between pegs when they score 8
points. That's because he is thinking about the numbers (i.e. the holes)
and not the things themselves (i.e. the spaces between the holes). Thus
for a score of 8 you leave 8 spaces between the pegs not 8 holes. This
also happens to be 7 holes. So, if we'd learn to distinguish the items
themselves from the spaces inbetween then we'd all be a lot better at this
whole addressing vs. counting thing.
____________________________________________________________________________
|
"A little nonsense now and then, | "If it walks out of the fridge, let
Is relished by the wisest men." | it go" -- John Dougherty
--W.W. | "If it loves you it will come back."
| -- Ian Davis
__________________________________|_________________________________________
Theta Xi
Kappa Sigma 1175
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: (Game) 80-digits Factoring Challenge
Date: 29 Jul 1999 23:50:22 GMT
>[EMAIL PROTECTED] writes (about that 80-digit number):
>So it's not a prime(?!) I'm not quite sure how Mathematica determines this,
>I think it uses the Miller-Rabin test, and I suspect that the test hasn't
>been validated for numbers of this magnitude. Any general comments on this
>would be most welcome.
If the number was a prime, we wouldn't need a program to factor it.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Prime numbers wanted
Date: Thu, 29 Jul 1999 23:03:21 GMT
Krunoslav Leljak wrote:
> // I would add this:
> if (temp % 2==0) temp++;
Well, the statement of what the function does
clearly specified that it takes an odd value.
If the caller is really only supposed to pass odd
numbers, then the code above could hide an error.
I'd suggest:
#include <assert.h>
...
assert(temp % 2 == 1);
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Prime numbers wanted
Date: Thu, 29 Jul 1999 20:05:25 GMT
Roger Carbol wrote:
> 1) How big is the longest complete list of primes generally
> available? How long is the last number?
> 2) Is there some sort of ongoing initiative (a la SETI@home) to
> add to this list?
The answer to 2 is, probably not, because the whole idea is dumb.
> Or is this another "making a list of all primes up to the 200 digit
> level would require turning every molecule in the universe into a
> computer and letting it run 15 billion years" issue?
And that's one reason why.
------------------------------
From: "Greg Keogh" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Fri, 30 Jul 1999 09:20:23 +1000
Hi from Melbourne Australia,
Just for your amusement, Mathematica 2.2.2 says:
In[4]:=
PrimeQ[256261430091697968103677033465028955910153603410170760238095478784430
33203276429]
Out[4]=
False
So it's not a prime(?!) I'm not quite sure how Mathematica determines this,
I think it uses the Miller-Rabin test, and I suspect that the test hasn't
been validated for numbers of this magnitude. Any general comments on this
would be most welcome.
Cheers,
Greg Keogh [EMAIL PROTECTED]
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Thu, 29 Jul 1999 17:42:14 -0700
Greg Keogh <[EMAIL PROTECTED]> wrote in message
news:Sk5o3.3$[EMAIL PROTECTED]...
> Hi from Melbourne Australia,
>
> Just for your amusement, Mathematica 2.2.2 says:
>
> In[4]:=
>
PrimeQ[256261430091697968103677033465028955910153603410170760238095478784430
> 33203276429]
> Out[4]=
> False
>
> So it's not a prime(?!) I'm not quite sure how Mathematica determines
this,
> I think it uses the Miller-Rabin test, and I suspect that the test hasn't
> been validated for numbers of this magnitude. Any general comments on this
> would be most welcome.
It's not a prime. But factoring it will require Quadratic Sieve, NFS, or
ECPP or some other big hammer. The simple algorithms all fail. It would
factor overnight on one of the workstations I have here. But I echo Bob
Silverman's question: "Why should I want to factor this number when I can
just as easily come up with a similar value that would be tough to factor?"
Is it a Charmichael number? Some other type of special pseudo-prime? What
brings this number to the fore as opposed to some other?
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: [EMAIL PROTECTED] (Paul Guertin)
Crossposted-To: alt.folklore.computers
Subject: Re: How Big is a Byte? (was: New Encryption Product!)
Date: Fri, 30 Jul 1999 08:30:43 +0900
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (Chris Hedley) wrote:
> In article <7msb7u$10j$[EMAIL PROTECTED]>,
> "Michael D." <[EMAIL PROTECTED]> writes:
> > I think that a major problem that we all have is that our mothers, yes, mine
> > as well as yours, taught us that the first number is one(1) rather than
> > zero(0).
> Which is a bit silly of them, really, considering their kids aren't born
> one year old, but zero years.
Except in Korea, and maybe other countries as well. A newborn is 1 year old
over there.
Paul Guertin
[EMAIL PROTECTED]
------------------------------
From: John Wasser <[EMAIL PROTECTED]>
Subject: Re: OK. Maybe I am missing something here.
Date: Thu, 29 Jul 1999 21:53:30 -0400
[[ This message was both posted and mailed: see
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <[EMAIL PROTECTED]>, Shktr00p1
<[EMAIL PROTECTED]> wrote:
> Take the ascii values of two characters one is from the file and one from the
> key.
>
> FILE: d (100) KEY: F (70) File+Key= �(170)
>
> You write ascii char 170 to the file as the encrypted byte.
>
> Now you use a file containing 1000 random bytes and use that as the key. I
> know "One-Time-Pad". Each file is encrypted with a password (8 bytes) as
> well.
> The password is used to encrypt the key file, then the key file is used to
> encrypt the file.
If you modify (encrypt) the key file doesn't that mean that you
can no longer decrypt the previously encrypted data?
Do you use a fresh password for every 1000 bytes? In a 10MB file
do you use 10,000 unique passwords?
------------------------------
From: [EMAIL PROTECTED] (Foghorn Leghorn)
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: 29 Jul 1999 21:00:51 -0500
On Fri, 30 Jul 1999 09:20:23 +1000, "Greg Keogh" <[EMAIL PROTECTED]>
wrote:
>So it's not a prime(?!) I'm not quite sure how Mathematica determines this,
>I think it uses the Miller-Rabin test, and I suspect that the test hasn't
>been validated for numbers of this magnitude. Any general comments on this
>would be most welcome.
Proving that a large number is prime can be a challenge, but you can
trust Mathematica when it says that the number is composite.
If n is the given number, we can quickly compute 2 to the n-1 modulo
n, and since the result is not 1, it follows that n is definitely
composite. In Mathematica, you can type
PowerMod[2,n-1,n]
to run the (weak) probable prime test for base 2. The theory for this
is Fermat's Little Theorem, which says that if p is prime and a is not
divisible by p, then a^(p-1) is congruent to 1 modulo p.
Foghorn Leghorn
[EMAIL PROTECTED]
------------------------------
From: "Kwong Chan" <[EMAIL PROTECTED]>
Subject: Re: Encrypting in C++ and C
Date: Thu, 29 Jul 1999 11:14:50 +0800
Try to get the length of the file, then use for or while loop.
Jeffery Nelson <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I've been working ok a "one pass pad" algorithm (if you can call it that),
> in C++ and have had many many troubles with they cypher turning the EOF
> character into some other letter and the other way arround. This becomes
> increasingly taxing when I use the .EOF to delimit my loops because I open
> the files in binary mode (although I can't open exe's for some odd
reason).
> Is there some way to end a loop at the END OF A FILE not useing .eof()? I
> know this isn't a C++ newsgroop, but because it is the cypher that is
> causing the problem, I thought someone here would have run into this. I
can
> give you the source to the file extractions method I use if you would
like,
> but I have to keep the header file I use to myself. Please HELP!
>
>
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: cryptography tutorials
Date: 30 Jul 1999 02:31:47 GMT
[EMAIL PROTECTED] (me) wrote:
>Parts of Menezes' book are at his web site.
>I have some classical crypto lessons by
>Randy Nichols, and the slides from Biham's
>cryptology course on my site. At Counterpane,
>Schneier offers a cryptanalysis course that
>will require a lot of reading.
>
Oh, and don't forget the US Army's Basic Cryptanalysis
Manual.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Snusk-Pelle)
Subject: Re: CSS/DVD Scrambler
Date: Fri, 30 Jul 1999 01:38:22 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 22 Jul 1999 10:03:17 GMT, [EMAIL PROTECTED] wrote:
>Is the CSS/DVD-style crypt algorithm available anywhere, or information
>about it? I know to read keys of the disk but that alone is rather
>useless.
>
>Or is it another of those things that can't be exported etc etc?
It's only available to companys producing DVD-players. They must
sign a NDA. There are some Linux programmers that has figured out
some of the CSS encryption algorithm. Here is a mailing list that
discusses CSS.
http://livid.on.openprojects.net/pipermail/livid-dev/
------------------------------
** 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
******************************
