Cryptography-Digest Digest #753, Volume #13 Mon, 26 Feb 01 19:13:00 EST
Contents:
Re: How to find a huge prime(1024 bit?) (Thomas Boschloo)
Re: How to find a huge prime(1024 bit?) (Paul Rubin)
Re: How to find a huge prime(1024 bit?) (Lynn Killingbeck)
Re: How to find a huge prime(1024 bit?) ("Brendan Shaw")
Was there ever a CRM-114 Discriminator? ("Mxsmanic")
Re: Arcfour in Ada (Thomas Boschloo)
Re: OverWrite freeware completely removes unwanted files from harddrive (those who
know me have no need of my name)
Re: "RSA vs. One-time-pad" or "the perfect enryption" ("Simon Johnson")
Re: Arcfour in Ada ("Julian Morrison")
Re: Rnadom Numbers (Benjamin Goldberg)
Re: SHA-1 (was Re: Password authentication ...) (Tim Tyler)
Re: Help Please !!!!!!!!!!!! ("Simon Johnson")
Re: how long can one Arcfour key be used?? ("Julian Morrison")
Re: Super strong crypto (wtshaw)
Viewable Picture Encryption ("Chase")
----------------------------------------------------------------------------
From: Thomas Boschloo <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
Date: Mon, 26 Feb 2001 22:00:18 +0100
Thomas Boschloo wrote:
> Hmm, maybe I can produce some high-school level proof of my
> assumptions..
>
> First: The density of primes is at average N/ln(N) from 2 until N IIRC
> (where N is e.g. a 512 bit number you will need for your P and Q).
>
> Second: Nope. I can't produce some examples at this (late) time of a few
> consecutive primes above some large (chosen) number.
Well, I want to thank you both for your replies and am somewhat
reassured that PGP 263i is safe because of the book published by 'Brandt
and Damg�rd' (I do not know their names however, nor do I posses the
book mentioned. At one time I wanted to order the book about EC by Neil
Koblitz from the same publisher, but it was far to expensive for me).
I can however proof that you can find a gap between primes of any size
to wish now (after a good nights sleep).
Take the proof for infinite primes by the greek. They use a number 'N'
that is composed by multiplying all the primes up to the largest prime
and adding 1. This new number can't be divided by any of the primes you
used to generate 'N' because e.g. the next increment of 'N' can be
divided by two, the next one by three, etc. They all just mis out, so
the new number 'N' must be a prime also! (Not only that, but it is
larger than the largest prime we assumed, thus falsifying the argument
that there is a largest prime).
Now, what if we don't take this number 'N' like the greek did, but the
number just /before/ 'N', dec('N')? This number can be divided by all
the primes we used in the greek example. Lets use an even more general
number and specify the number P(1..x), meaning all the numbers from 1
till x multiplied together. This number can be divided by any number
between and including 1 and x.
If we skip the first successor of this new number P(1..x), we obviously
get a prime. The next however will be dividable by the prime number 2,
and the next by the also prime number 3, and the next will be dividable
by 4, etc. So in fact, I have proven that in the distribution of prime
numbers, you can find a gap of ANY length you like. The gap in the
previous example is e.g. x-1, and maybe even larger. Now what does this
mean if we still want the number of primes until 'N' to approach
N/ln(N)? (I can't prove this fact myself, but I have a book that has the
proof for this I think). Well, if there are large gaps like this (and I
don't feel like calculating P(1..x)/log(P(1..x)), I guess it is getting
late again), maybe there are also places where there are a lot of prime
numbers after one-other. Which the prime generation methode of PGP 263i
will (statistically) MISS!!
I still am not smart enough to prove there are places where there are a
lot of prime numbers after one another, but I hope I have shown that
there are also places where there are large gaps between them. Maybe
more than N/ln(N).
BTW I now realize that P(1..x) can be written as x! (stupid me!)
Can some of you guys calculate x!/ln(x!) for me? (please)
Regards,
Thomas
--
Jessica "I'm not bad, I'm just drawn that way"
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
Date: 26 Feb 2001 13:42:14 -0800
Thomas Boschloo <[EMAIL PROTECTED]> writes:
> Can some of you guys calculate x!/ln(x!) for me? (please)
Use Stirling's approximation:
x! ~= (x/e)^x * sqrt(2*pi*x) * (1 + 1/(12x) +...)
------------------------------
From: Lynn Killingbeck <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
Date: Mon, 26 Feb 2001 22:11:02 GMT
Thomas Boschloo wrote:
>
> Thomas Boschloo wrote:
>
> > Hmm, maybe I can produce some high-school level proof of my
> > assumptions..
> >
> > First: The density of primes is at average N/ln(N) from 2 until N IIRC
> > (where N is e.g. a 512 bit number you will need for your P and Q).
> >
> > Second: Nope. I can't produce some examples at this (late) time of a few
> > consecutive primes above some large (chosen) number.
>
> Well, I want to thank you both for your replies and am somewhat
> reassured that PGP 263i is safe because of the book published by 'Brandt
> and Damg�rd' (I do not know their names however, nor do I posses the
> book mentioned. At one time I wanted to order the book about EC by Neil
> Koblitz from the same publisher, but it was far to expensive for me).
>
> I can however proof that you can find a gap between primes of any size
> to wish now (after a good nights sleep).
>
> Take the proof for infinite primes by the greek. They use a number 'N'
> that is composed by multiplying all the primes up to the largest prime
> and adding 1. This new number can't be divided by any of the primes you
> used to generate 'N' because e.g. the next increment of 'N' can be
> divided by two, the next one by three, etc. They all just mis out, so
> the new number 'N' must be a prime also! (Not only that, but it is
> larger than the largest prime we assumed, thus falsifying the argument
> that there is a largest prime).
Not correct, here. This is the proof that there is no largest prime.
When you compute 1*2*...*N+1, then either: (1) this number is also a
prime, and larger than N; or (2) there is a prime larger than N that
divides this number. In either case, there is a prime larger than N,
completing the proof-by-contradiction. Your statement that this number
is necessarily prime, is not a correct statement (but, it is a common
mis-statement!). Try N=4, for example, where 1*2*3*4+1=25 is not prime.
> (snip)
>
> If we skip the first successor of this new number P(1..x), we obviously
> get a prime. The next however will be dividable by the prime number 2,
> and the next by the also prime number 3, and the next will be dividable
> by 4, etc. So in fact, I have proven that in the distribution of prime
> numbers, you can find a gap of ANY length you like. The gap in the
> previous example is e.g. x-1, and maybe even larger. Now what does this
> mean if we still want the number of primes until 'N' to approach
> N/ln(N)? (I can't prove this fact myself, but I have a book that has the
> proof for this I think). Well, if there are large gaps like this (and I
> don't feel like calculating P(1..x)/log(P(1..x)), I guess it is getting
> late again), maybe there are also places where there are a lot of prime
> numbers after one-other. Which the prime generation methode of PGP 263i
> will (statistically) MISS!!
>
Your statement about "a lot of prime numbers after one-another" does not
make sense (to me, anyway). If N is a prime, then N+1 is necessarily
not a prime, for N>2. There is also a famous twin-prime conjecture about
the number of times that N and N+2 are both prime. Your statement seems
to mean something else, but I'm not sure just what.
> I still am not smart enough to prove there are places where there are a
> lot of prime numbers after one another, but I hope I have shown that
> there are also places where there are large gaps between them. Maybe
> more than N/ln(N).
>
> BTW I now realize that P(1..x) can be written as x! (stupid me!)
>
> Can some of you guys calculate x!/ln(x!) for me? (please)
>
> Regards,
> Thomas
> --
> Jessica "I'm not bad, I'm just drawn that way"
------------------------------
From: "Brendan Shaw" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: How to find a huge prime(1024 bit?)
Date: Mon, 26 Feb 2001 22:20:08 -0000
Just being picky ... multiplying the first N primes p1->pN and adding one
does not necessarily generate a prime number. Sometimes it does, sometimes
it doesn't. I don't know if it does infinitely many times? However one can
use it to argue for a prime larger than pN, since either the product+1 is
prime (and greater than pN) or else it must divide by some prime larger than
pN (since it clearly doesn't divide by p1 thru pN).
Brendan
>
> "Thomas Boschloo" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > [CC-ed: to sci.crypt for a professional opinion]
> >
> > An Metet wrote:
> >
> > > >How to find a huge prime(1024 bit?)
> > >
> > > Select a big random number, try to divide it by small numbers
> > > first, then search for `Rabin-Miller� primality test at google. If
that
> > > fails, increase the number and repeat the above.
> >
<snip>
> >
> > The Greek however proved that if you had some 'largest' prime number,
> > you could just multiply all primes until that prime number, add one and
> > then you would have created a prime that was even 'larger'. So there is
> > an endless supply of primes (although they may become a little far
> > appart or they might become hard to 'prove' to be prime).
> >
> > Thomas
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: Was there ever a CRM-114 Discriminator?
Date: Mon, 26 Feb 2001 22:23:32 GMT
In Kubrick's classic film _Dr. Strangelove_, airborne SAC bombers use an
encryption device called a CRM-114 Discriminator to receive encrypted
communications from the ground. The device required a three-letter key
(which doesn't sound very secure). Was there ever such a device
actually in use?
------------------------------
From: Thomas Boschloo <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.ada
Subject: Re: Arcfour in Ada
Date: Mon, 26 Feb 2001 23:41:50 +0100
Julian Morrison wrote:
>
> http://download.sourceforge.net/fling/arcfour-ada-1.0.0.tar.gz
>
> This code has been created for use with the Fling project
> (http://fling.sourceforge.net/).
>
> This is ArcFour (Alleged RC4), CipherSaber variant, capable of
> CipherSaber-1 and CipherSaber-2. It is coded in Ada, and is dependent on
> AUnit and Formatted_Output (available via the AdaPower site). It's
> probably pretty GNAT-dependent too, since I've had no need to compile it
> anywhere else. If you want fixes, send patches and/or bug reports via
> Fling's SourceForge patch tracker.
>
> This code has been placed in the public domain by its author.
>
> Release notes: first full release, all unit tests pass, but it may be
> implementation dependant.
http://fling.sourceforge.net/wiki/index.php?full=arcfour
Why did you decide to go for arcfour and not the AES
http://www.nist.gov/aes ? AFAIK Arcfour or RC4 was originally a
'security by obscurity' cypher (Arcfour was (now illegal) reverse
engineered from RC4 by www.rsa.com).
I understand that you might like the idea of a stream-cypher for data
transmission, but aren't stream and block cyphers thought to be somewhat
identical in functionality by cryptographers?
Couldn't you just use the 128 bit block size of Rijndael as a (somewhat
small) buffer for your traffic? Be honest, what would be the overhead
from the 128 bit boundaries?
AES seems so much more secure in the long run than RC4!
(note: I am not a cryptographer nor have I every implemented a cypher)
Thomas
(BTW I do sympathize with your cause of an anonymous TCP/IP protocol.
Good luck!)
--
Jessica "I'm not bad, I'm just drawn that way"
------------------------------
From: [EMAIL PROTECTED] (those who know me have no need of my name)
Crossposted-To: alt.hacker
Subject: Re: OverWrite freeware completely removes unwanted files from harddrive
Date: Mon, 26 Feb 2001 22:58:10 -0000
<[EMAIL PROTECTED]> divulged:
>Benjamin Goldberg wrote:
>
>> There isn't, however, any such command or function in dos/win.
>
>Of course there is.
>
>http://www.sysinternals.com/ntw2k/utilities.shtml
also work-arounds, e.g., close(dup(fh)), which is effective back to v2.0x
of msdos if i remember correctly. in fact some libraries did that when
running under dos versions that didn't support fsync() directly (i.e.,
prior to 3.10 or there about).
--
okay, have a sig then
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Mon, 26 Feb 2001 23:24:13 -0800
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> William Hugh Murray wrote:
> > Modern cryptography is not provable or perfect. However, it is
> > demonstrably, as opposed to provably, good enough, as opposed to
> > perfect.
>
> I would like to see such a demonstration. What threat model
> are you assuming, against high school hackers?
Actually, that isn't such a bad threat model. There are not that many
goverments or large corporations in comparision to the vast numbers of
l33t|sts. And lets face it, when you look at your firewall log most of the
scans/port-probes etc. are by things like BO2k and SubSeven, hardly the
standard tools of much more highline counterparts, such as the NSA.
In my humble opinion, cryptography is designed to protect us from around 90%
of attack. The ten remaining 10% of attacks that get through usually have
nothing to do with actual enciphering technology. I'd say alot of them are
achieved by threat: "Give me your password, or I break your neck." and still
more by key-loggers. Ask yourself the question, What is the point of having
SHA-1 to hash your passwords, when in 30 seconds I can break into your house
and install a key logger?
I believe the ultimate problem with most threat models is this:
When Alice and Bob communicate, they assume that Alice's and Bob's machines
are completly secure and when Mallory goes to work, people assume he always
picks the thing of intellectual intrest to attack.
Simon.
------------------------------
From: "Julian Morrison" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.ada
Subject: Re: Arcfour in Ada
Date: Mon, 26 Feb 2001 23:20:23 +0000
"Thomas Boschloo" <[EMAIL PROTECTED]> wrote:
> Why did you decide to go for arcfour and not the AES
> http://www.nist.gov/aes ?
> [...]
>
> AES seems so much more secure in the long run than RC4!
AFAIK, the AES cypher is more secure in that you can safely reuse keys.
It's also newer, though, and new crypto is less trustable. AES is also a
very gread deal more CPU churn and overhead than Arcfour. Since you can
only encrypt in blocks of four bytes, you need extraneous header info to
show where the contents end, and you need to CBC the blocks together. If
you're encrypting a lot of small things (such as in Fling's routeballs)
the overheads will add up.
>From what I've understood from older messages here, Arcfour is "good
enough" for the task at hand. Of course, if anyone knows I got this
wrong, please do say.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Rnadom Numbers
Date: Mon, 26 Feb 2001 23:16:28 GMT
Douglas A. Gwyn wrote:
>
> Simon Johnson wrote:
> > yeah, good point. I assume that this question cannot be answered
> > then until the problem surrounding p=np is solved, right?
>
> P?=NP has absolutely nothing to do with whether a PRNG output can
> be successfully cryptanalyzed.
Well, not "nothing", but little -- depending on the exponent found in
the case that P=NP. If P=NP, and an algorithm is found to solve NPC
problems in O(N^6), then many currently 'secure' prngs would be
considered broken.
If the cipher takes polynomial for the PRNG to generate each bit, then
creating a 3SAT problem describing the bits of the output in terms of
bits of key also takes polynomial time. Convert this SAT to 3SAT,
substitute in known PRNG outputs, and solve using the NPC solver.
If P!=NP, or the exponent for N is large, then P?=NP is not a concern.
IIRC, from a problem I did awhile ago, If our P=NP solver takes O(N^18)
time, and we have a 128 bit key, then it takes approximatly O(2^126)
time for the NPC solver to break the system.
--
A solution in hand is worth two in the book.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: SHA-1 (was Re: Password authentication ...)
Reply-To: [EMAIL PROTECTED]
Date: Mon, 26 Feb 2001 23:13:39 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote:
: Have you repeated the test? [...]
No - I just wondered if you were doing something obvious wrong.
AFAICS, you weren't; implementation issues remain a possibility.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Help Please !!!!!!!!!!!!
Date: Mon, 26 Feb 2001 23:29:16 -0800
PADDOCK <[EMAIL PROTECTED]> wrote in message
news:97e3mn$774$[EMAIL PROTECTED]...
> the following is a list of unix crypt passwords
>
> have broken 15 of them using John the ripper and crack etc
> but can't get the rest - any ideas u clever bods?
> thanks
> a novice
Yes, brute force them yourself., that is try every possible pasword until
you hit on one.
> nbr:NgrdOQvGJxApM:Brian Randell
> nim2:PZ.Gm3kItDUbo:Isi Mitrani
> nsks:r/3cSTl4rxPSo:Santosh Shrivastava
> npal:kS6W7H2qpQhYY:Pete Lee
> nta:PndNNaaMSMhOQ:Tom Anderson
> ncbj:6RERTsaF2WR1U:Cliff Jones
> nay:Y709XJm2HUfx6:Alex Yakovlev
> nmk:JgcQaXcjborkI:Maciej Koutny
> njll:8cV7NUYoDXjkY:John Lloyd
> npw:u4kASSO9cX0No:Paul Watson
> nrjs:BOaxJuED4sH5w:Robert Stroud
> ncp:Nn9Zpg0p7d.b2:Chris Phillips
> ncrs:2AaawqgIu1edA:Dick Snow
> nkw:UJ5TNpOBjOIkg:Ken Wright
> nbnr:ZFzRNtiqA.HXE:Nick Rossiter
> nmrm:jAIqtDEolVKxY:Martin McLauchlan
> namk:MYp383eEKVBQI:Albert Koelmans
> nlfm:n3CcSAUEnkt/Q:Lindsay Marshall
> npde:XywybIkyCZfDU:Paul Ezhilchelvan
> nnas:JAnkXNWjFRmV2:Neil Speirs
> ncmh:LDJXyq4LvdXjA:Chris Holt
> njsf:fxbrIoGv8skMY:John Fitzgerald
> nljs:yPBPydZVb2oV.:Jason Steggles
> ngm:Eup9.OnZ04AsM:Graham Morgan
> nsr:RYxOLUe9WjyZU:Steve Riddle
> nnfh:ngowr/aPxnqI6:Nigel Hall
> ngmt:B0E/VlmjOvSbo:Gerry Tomlinson
> ncrr:urUg1XGMqAvuY:Chris Ritson
> njkw:ocKDxwrevSQqw:Jim Wight
> ndiw:0bfwV7bYHkCu6:Iain Wood
> namb:H9v93uDQFy10g:Alex Barfield
> njhw:ChNBCoq/AUsuo:Jon Warwick
------------------------------
From: "Julian Morrison" <[EMAIL PROTECTED]>
Subject: Re: how long can one Arcfour key be used??
Date: Mon, 26 Feb 2001 23:49:15 +0000
"Simon Johnson" <[EMAIL PROTECTED]> wrote:
> I think I remember for an average key it is something like a few
> gigabytes before a bias can be detected in the output. Not sure if this
> is correct though?
Thanks :-)
Also, does anyone know how this varies with key length and
number-of-mixes (N in CipherSaber-2)?
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Super strong crypto
Date: Mon, 26 Feb 2001 17:20:48 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> As to key recovery, my working assumption is that we are
> trying to figure out what form a realization of the subject
> (super strong crypto) might take. *If* one has a basic
> (e.g. block encipherment) component suitable for use in
> such a scheme, then there is negligible chance that any
> isolated key could be recovered. My straw man proposal
> takes that as a starting place and build on it in an
> attempt to avoid the obvious theoretical weakness of
> stretching a small amount of key information over a long
> span of encryption, as is often done in current (public)
> systems. The suggestion is that something of the sort
> might be a necessary component of any practical "super
> strong crypto" system.
Changing keys is like changing your underwear and socks, if they smell,
you waited too long.
There are many ciphers with an unknown threshold for safe ciphertext under
a specific key. For those, it's still good to periodically change keys as
good security policy; for those with a definite threshold, usually all too
short, changing keys may merely mean isolating messages, requiring brute
forcing of each individual message.
--
Better to pardon hundreds of guilty people than execute one
that is innocent.
------------------------------
Reply-To: "Chase" <[EMAIL PROTECTED]>
From: "Chase" <[EMAIL PROTECTED]>
Subject: Viewable Picture Encryption
Date: Tue, 27 Feb 2001 00:05:14 GMT
I have come up with an interesting concept that I would like to attempt to
code, using Visual C++ 6....Here it goes:
When encrypting most types of data, all the bits are shifted/reorganized..
For example, when you encrypt a text file, you can view the encrypted
contents on like Notepad or whatever, but say, if you are trying to encrypt
a JPG or BMP file, you can't open it, because the header that delinates the
file as a .JPG or .BMP file is also scrambled. I would like to try and have
it so that If I encrypt a JPG or BMP file, that it is still viewable in a
JPG or BMP viewer, but the actual picture contents are scrambled...so
essentialy, you'd be opening a picture file with all the picture information
viewable, but scrambled. Does anyone have any idea how I can go about doing
this? Any ideas would be very much appreciated.
-Chase
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
