Cryptography-Digest Digest #179, Volume #14 Thu, 19 Apr 01 00:13:00 EDT
Contents:
Re: Crypto question (Bill Unruh)
Re: Proof of RSA ("Scott Fluhrer")
Prime Numbers Patterns? ("Wizartar")
WHY I HATE BOSCHLOO (Fight Boschloo)
Re: I took the $5000 Goldman Challenge (Dror Baron)
Re: Current best complexity for factoring? ("Joseph Ashwood")
Re: Prime Numbers Patterns? ("AY")
Re: Crypto question ("Joseph Ashwood")
ECC-109P Challenge Clients are available ("Tom St Denis")
Easy web based email service? ("black")
Re: Easy web based email service? (Paul Rubin)
Re: Easy web based email service? ("Tom St Denis")
Re: Crypto question (John Savard)
Re: Reusing A One Time Pad ("Mark G Wolf")
CAST5 Implementation (George)
random square factoring? ("Tom St Denis")
Re: A practical idea to reinforce passwords (Thomas Wu)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Crypto question
Date: 18 Apr 2001 23:11:06 GMT
In <9bl0dm$[EMAIL PROTECTED]> "Shah Karim" <[EMAIL PROTECTED]> writes:
]The problem I have is where the receiver decodes the sender's digital
]certificate: How can the receiver decode something that is encoded with the
]sender's *private* key? To put it another way, Alice encodes a message using
]her *private* key and sends it to Bob. How can Bob decode that message using
]Alice's *public* key? Is this normal? My understanding is that Alice can
]only encode messages using Bob's public key, and Bob then will decode that
]message using his private key.
Encrypting and decrypting is commutative.
E(D(M))=D(E(M))
Ie the receiver encrypts with the senders public key the message which
te sender decrytped with his private key.
Ie, botht he private and public key work equally well for encoding and
decoding.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Proof of RSA
Date: Wed, 18 Apr 2001 16:15:52 -0700
Bill Unruh <[EMAIL PROTECTED]> wrote in message
news:9bkh2b$q2i$[EMAIL PROTECTED]...
> In <[EMAIL PROTECTED]> sianglin <[EMAIL PROTECTED]> writes:
>
> >Can someone prove that, in RSA, D(E(M)) = M where M=message,
> >E=Encryption, D=Decryption?
> Would not be worth too much if this were not true, would it?
Actually, there have been public key cryptosystems proposed where you cannot
uniquely decrypt all messages, only the vast majority of them.
One example which springs to mind is the RSA variant (proposed by Takagi)
where the modulus is not square-free: the modulus might be p*p*q.
Obviously, given any plaintext of the form k*p*q, you always get a
ciphertext of 0, and therefore in that system, D(E(M))=M is *not* a theorem.
Of course, it is a thereom in RSA. My point is that you can not trivially
conclude that from the fact that RSA is considered useful.
>
> Uses
> If A<pq (where p,q primes) and ed=1 mod(p-1)(q-1)
> then
> A^(ed)=A mod pq
> A^e mod pq is the encrypted text. Then (A^e mod pq)^d mod pq = A^ed mod pq
>
>
>
------------------------------
From: "Wizartar" <[EMAIL PROTECTED]>
Subject: Prime Numbers Patterns?
Date: Thu, 19 Apr 2001 00:31:18 +0100
Hi,
Is there any logic to prime numbers, I've been doing a study of them for a
computer course and still have a long way to good before I get a paper
together.
For an example of what I mean:
All numbers ending in 0, 2, 4, 5, 6, 8, once you get above 9 are defiantly
not a prime numbers. So only numbers ending in 1, 3, 7, 9 need to be
tested. Are there any other common patterns, once you reach higher numbers?
Any help would be useful,
Wiz
------------------------------
Date: 18 Apr 2001 23:38:00 -0000
From: [EMAIL PROTECTED] (Fight Boschloo)
Subject: WHY I HATE BOSCHLOO
Crossposted-To: alt.privacy.anon-server,alt.security-pgp
I hate Boschloo
===============================================
HISTORY:
That Boschloo bozo is a clown and a troll who has been looming around for nearly a
year.
Don't mistake a "regular" (troll) with a knowledgeable person: that self-proclaimed
"security expert" is not even a remailer user. In the past, he proved himself unable
to check a PGP signature, and got ridicule from every single technical topic he wanted
to talk about.
Besides false or inaccurate or misleading technical misinformation, his posts are
about his avowed mental illness, or for bashing remops or real freedom fighters: he
likes to quarrel with every one, and stir shit. Sometimes, it is even pure delirium
(when he misses his pills?)
One of his last actions was to stage a hoax about his own suicide, just to try to grab
some sympathy, after he had been exposed as a troll and technically incompetent.
The worst being his teasing of Script-Kiddie until it triggered a new flood on apas.
Of course, he refuses to apologize.
Actually, the level of contempt he shows for remailer users:
they don't give their names, while he does
that can't do anything against him, without giving their names
is in no way different from what is displayed by Pangborn, Burnore and the like
Ignore him completely, killfile him, respect others' killfiles
KILLFILE:
To put him in your killfile, put "Author: Boschloo"
That will make disappear both him and people who warn about him
If you want to tell him to buzz off, or warn about him,
use a nickname containing "Boschloo" (Boschloo Hater, Boschloo Sucks,...)
to accomodate such killfile for "regulars", and still warn newbies
COURAGE:
Boschloo is getting _no_ answer from apas any more.
He has to crosspost to various newsgroups to try to grab some attention.
In a few months, it will be gone.
------------------------------
Crossposted-To: comp.compression
From: Dror Baron <[EMAIL PROTECTED]>
Subject: Re: I took the $5000 Goldman Challenge
Date: Wed, 18 Apr 2001 19:00:46 -0500
On Wed, 18 Apr 2001, Tom Gutman wrote:
> > > Geometry he would get lost. Its hard to mix the two geometres so
> > > I try to be of the type uses which ever one fits the problem.
> > > One has to be flexable.
> >
> > Dude, I rest my case. That's like cheating whichever
> > way works best for any given problem.
> >
> That's kind of weird! So you think it's like cheating for me to
> decide whether I should use a hammer or a screwdriver after
> examining the fastener?
He isn't only changing his tools. He is changing his
problem-definitions. Every time he adapts the rules,
the operating system, the way he determines the length,
every time he uses the most convenient set of rules.
Dror
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Current best complexity for factoring?
Date: Wed, 18 Apr 2001 17:03:02 -0700
Well if that doesn't work for you try:
pick a random number
repeat until prime
It'll work, but it'll be a slower process. You could also do
pick a random odd number
here:
add random even number
if number is not prime goto here
or any of a million or so other options
They will all work, the add 2 method was chosen because while the bias
towards primes that comes after strings of composites is there, it is not
known how to determine which primes come after such a stream, and it is
known that the number of primes of size 512-bits is already greater than the
2^128. Given this unless someone finds a factoring algorithm that is easier
when the primes come after a long stream of composites, there is no
additional risk. Since it is approximately equally probable that someone
will find a factoring algorithm that will depend on the primes coming after
a short stream of composites as a long stream, both are equally secure.
Joe
"Terry Boon" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Wed, 11 Apr 2001 06:37:36 GMT, Samuel Paik <[EMAIL PROTECTED]> wrote:
> >Claus N�veke wrote:
> >> How are these primes generated? I thought they are too big for doing
> >> math-operations with them...
> >
> >The second question first. Use multi-word computations--limit is only
> >memory and time.
> >
> >Generally, pick random odd n-bit number (this means the high order
> >bit and low order bit are set to 1 and the rest of the bits are chosen
> >randomly). Test for probabilistic primality. If not prime, increment by
2
> >and go to test, otherwise, accept as prime.
>
> I've seen this method suggested elsewhere as well...
>
> Does this not bias the "random" selection of a prime towards primes
> which come after a long run of composites?
>
> (And, furthermore, is this effect significant? I wonder if I've got a
> pmf for the spacing between primes somewhere in my bookshelf...)
>
> I suspect that the answers to these two questions are "Yes" and "No"
> respectively.
>
> - --
> Terry Boon, Hertfordshire, UK
> [EMAIL PROTECTED]
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.0.4 (GNU/Linux)
> Comment: Processed by Mailcrypt 3.5.5
>
> iD8DBQE63ftpB+GG7A6DEUARAi13AJ4osqMvrFyGH4O8BI+G4UpiEtUUWACfdOqh
> LmzEwl6vjEbu0ErBu5C6PoA=
> =uux2
> -----END PGP SIGNATURE-----
------------------------------
From: "AY" <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Patterns?
Date: Thu, 19 Apr 2001 01:28:12 +0100
I think the Riemann Hypothesis is somewhat related to your question, if not
exactly. It is nonetheless quite interesting.
see:
http://www.claymath.org/prize_problems/riemann.htm
http://www.utm.edu/research/primes/notes/rh.html
For a discussion on primality tests (and much more), see Chapter 4 of HAC.
http://www.cacr.math.uwaterloo.ca/hac/
Also, something that everyone should know (but not discussed in HAC!) is
that the digits of a multiple of 3 always add up to a multiple of 3 (think
recursion). I just wonder if there's a big list of such curiosities
somewhere?
AY
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Crypto question
Date: Wed, 18 Apr 2001 17:10:23 -0700
I see everyone else has answered in accordance with RSA. Which is fairly
typical because it is the best known algorithm, and what you were asking is
easiest to see there. In particular when choosing an RSA key-pair you
generate a triple (a,b,N), then you decide whether a or b is the public key.
Or at least you can, generally other tricks are used, like setting the
public key to 65537, but that is not necessarily the case.
With signature algorithms based on other problems, typically DLP or a
varient, the proofs are much more involved, instead of recreating them here
I suggest you grab the DSA FIPS and read the proof there. Although you
wouldn't know from looking at it, the DSA proof is actually a fairly simple
one for an "alternative" digital signature proof.
If you have any questions about it, either I or someone else here can answer
them.
Joe
"Shah Karim" <[EMAIL PROTECTED]> wrote in message
news:9bl0dm$[EMAIL PROTECTED]...
> OK I am a crypto newbie, and while doing some reading on public key
> cryptography and digital signatures, I ran into something which puzzles me
:
>
> Given:
>
> 1) In public key cryptography there are 2 keys, private key and public
key,
> and only the public key is published. So anyone can send a message to an
> intended recipient using that recipient's public key to encrypt that
> message. However, only the intended recipient can decode that message
> because they have the private key.
>
> 2) In sending a digital signature, the sender computes a message digest
from
> the message to be sent, using for example a one-way hash function. This
> digest is encrypted using the sender's *private* key, yielding a digital
> signature. This signature, along with the original message to be sent, is
> encrypted using the intended recipient's public key and sent.
>
> 3) The recipient uses his private key to extract the message and the
> encrypted digital signature. Now to verify the signature, the recipient
> decrypts it using the sender's *public* key, yielding the original message
> digest. He also takes the received message and computes the digest using
the
> same one-way hash function. Lastly he compares the two digests to make
sure
> that they match, ensuring the message has not been tampered with in
> transmission.
>
> The problem I have is where the receiver decodes the sender's digital
> certificate: How can the receiver decode something that is encoded with
the
> sender's *private* key? To put it another way, Alice encodes a message
using
> her *private* key and sends it to Bob. How can Bob decode that message
using
> Alice's *public* key? Is this normal? My understanding is that Alice can
> only encode messages using Bob's public key, and Bob then will decode that
> message using his private key.
>
> Can anyone explain/ comment on this? Thanks.
>
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: ECC-109P Challenge Clients are available
Date: Thu, 19 Apr 2001 02:04:39 GMT
I don't speak for the ECC-109P team but they have clients available for
anyone wanting to join in the search for a solution to the ECC DLP challenge
(prime of order 109 bits).
Clients and info at
http://www.nd.edu/~cmonico/eccp109/
What would be cool is if they had more technical stuff about the math they
are using to attack the DL problem.
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: "black" <[EMAIL PROTECTED]>
Subject: Easy web based email service?
Date: Wed, 18 Apr 2001 19:00:11 -0700
Is there an easy to use web based email service that encrypts both ways
between my PC and
the remote encrypting server and then encrypts/decrypts messages passing
beyond the encrypting server
to the outside world?
In a nutshell something that lets me correspond email with users who do use
encryption but without
my mail being readable by my local system administrator or by the ISP we
use.
Dilbert needs such a service!
Does not need to be a free service but not too expensive as it is for
personal use.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Easy web based email service?
Date: 18 Apr 2001 19:16:28 -0700
"black" <[EMAIL PROTECTED]> writes:
> Is there an easy to use web based email service that encrypts both
> ways between my PC and the remote encrypting server and then
> encrypts/decrypts messages passing beyond the encrypting server to
> the outside world?
Hushmail.com is probably pretty close to what you want.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Easy web based email service?
Date: Thu, 19 Apr 2001 02:16:36 GMT
"black" <[EMAIL PROTECTED]> wrote in message
news:pLrD6.88$[EMAIL PROTECTED]...
> Is there an easy to use web based email service that encrypts both ways
> between my PC and
> the remote encrypting server and then encrypts/decrypts messages passing
> beyond the encrypting server
> to the outside world?
>
> In a nutshell something that lets me correspond email with users who do
use
> encryption but without
> my mail being readable by my local system administrator or by the ISP we
> use.
> Dilbert needs such a service!
>
> Does not need to be a free service but not too expensive as it is for
> personal use.
Spend 10 minutes and learn how to use PGP.
Nuff said.
Tom
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Crypto question
Date: Thu, 19 Apr 2001 02:39:09 GMT
On Wed, 18 Apr 2001 16:18:18 -0500, "Shah Karim"
<[EMAIL PROTECTED]> wrote, in part:
>The problem I have is where the receiver decodes the sender's digital
>certificate: How can the receiver decode something that is encoded with the
>sender's *private* key?
Because he knows the sender's *public* key.
The private key and the public key - each one stands to the other key
in the same relationship.
x^e mod M is decoded by raising it to d mod M, to get x back;
x^d mod M is decoded by raising it to e mod M, to get x back.
In the first case, x is encrypted, because only the key owner knows d,
and can decrypt x^e mod M to get x.
In the second case, x is signed, because only the key owner knows d,
and could have encrypted x.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Wed, 18 Apr 2001 22:09:40 -0500
> Ah. It is called "Snake Oil".
Yeah but can you really make oil from snakes, or is that the joke.
------------------------------
From: George <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: CAST5 Implementation
Date: Wed, 18 Apr 2001 22:26:17 -0500
Hello everyone. I've been trying to implement CAST5, but I am obviously
doing it incorrectly because the test vectors do not match up. I have
looked at other source code examples and am having no success in finding
my mistake(s). Could someone please post an extended vector test?
(showing the values of the Kr and Km arrays when using a 128 bit key,
what the values for the left and right halves shouldbe after each round,
etc.) Thanks.
-George
[EMAIL PROTECTED]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: random square factoring?
Date: Thu, 19 Apr 2001 03:42:08 GMT
As something to fill time between star trek and croc hunter... I tried
adding a "random square" method to my factor program (still waiting for the
koblitz book)
Basically it works like this
1. Pick X and Y at random
2. If X^2=Y^2 (mod N) then see if gcd(X-Y,N) is a factor
3. X = X^2 + 1 mod N
4. Y = Y^2 + 1 mod N
5. Goto 2
It doesn't seem to be able to factor anything. I thought it would be a
birthday paradox thingy... where it's about sqrt(N) work... but when I try
to factor small numbers like N=1234567 it doesn't work!
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: A practical idea to reinforce passwords
Date: 18 Apr 2001 20:46:03 -0700
[EMAIL PROTECTED] (Harald Korneliussen) writes:
> My idea is that upon selecting a password, X bits of
> random data is added to the password. You are not
> informed of what these bits are, nor does the computer
> store them. The computer only stores how many bits
> there are, and brute-forces them every time you enter
> you password.
> The reason this is a good idea is: It only adds a few
This isn't really a good idea. The problem is, you slow down
a legitimate login by the same factor that you slow down an
attack. It's easy to come up with slow hashes that make
everything slower, the real innovation is with methods that
make a brute force attack exponentially harder while having
less of an impact on legitimate users, say a linear workfactor
difference.
> If there is something wrong with this approach, or if
> it is for some reason impractical, please tell me!
It's impractical in the sense that it doesn't offer any improvement
to the existing state-of-the-art in terms of security/convenience
tradeoffs.
> Harald Korneliussen
>
> ______________________________________________________
> Do You Yahoo!?
> Organiser sammenkomsten p� http://no.invites.yahoo.com
>
> --
> Posted from web3001.mail.yahoo.com [204.71.202.164]
> via Mailgate.ORG Server - http://www.Mailgate.ORG
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
** 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
******************************
