Cryptography-Digest Digest #946, Volume #9 Wed, 28 Jul 99 15:13:04 EDT
Contents:
___EllipticCC on a GemXpresso JAVA card (kctang)
Re: Novice key question ("Mark Hammer")
With all the talk about random... ("Jeffery Nelson")
Re: hush mail (Albin Zuccato)
Re: What the hell is XOR? (John Savard)
Re: (Game) 80-digits Factoring Challenge (Glenn Davis)
Re: With all the talk about random... (John Savard)
Re: Is breaking RSA NP-Complete ? (Anton Stiglic)
Re: Standard Hash usage (Anton Stiglic)
decode base64 (John Xiao)
Anyone knows where to get original encryption source code? ("Digital")
Anyone knows where to get original encryption source code? ("Digital")
Re: (Game) 80-digits Factoring Challenge (Jim Gillogly)
Re: (Game) 80-digits Factoring Challenge (Roger Carbol)
the defintion of Entropy (Anton Stiglic)
Re: Standard Hash usage (Anton Stiglic)
Re: (Game) 80-digits Factoring Challenge (Bob Silverman)
Prime numbers wanted ("Vincent")
Re: (Game) 80-digits Factoring Challenge (Jim Geary)
Re: (Game) 80-digits Factoring Challenge ("Dann Corbit")
Re: (Game) 80-digits Factoring Challenge (Bob Silverman)
Re: With all the talk about random... ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: kctang <[EMAIL PROTECTED]>
Subject: ___EllipticCC on a GemXpresso JAVA card
Date: Wed, 28 Jul 1999 20:56:32 +0800
Dear all,
I am asking your opinion on implementing an Elliptic Curve Crypto
system (maybe just a signature scheme) on a GemXpresso Java Card.
The characteristics of this JAVA card can be found on:
http://www.gemplus.com/products/microprocessor/gemxpresso.htm
Note that it has a 5Mhz 32-bit cpu and 32 kbyte EEPROM, but no
crypto-coprocessor.
But it runs JAVA and JAVA seems to be slow.
So is it FEASIBLE to run ECC signature on a GemXpresso JAVA card
even if one trys the best to implement a state-of-the-art efficient
ECC?
(e.g. Does it possess a JAVA JIT?
Can it run assembly language?)
Yours, kctang
------------------------------
From: "Mark Hammer" <[EMAIL PROTECTED]>
Subject: Re: Novice key question
Date: Wed, 28 Jul 1999 09:33:32 -0700
I meant to say a numerical key (from text password).
--
Mark Hammer
[EMAIL PROTECTED]
http://free.prohosting.com/~maqua/
Mark Hammer <[EMAIL PROTECTED]> wrote in message
news:7nlgjb$5ljk$[EMAIL PROTECTED]...
> I am wondering how algorithms generate a key if the user inputs a
password.
>
> --
>
> Thanks,
> Mark Hammer
> [EMAIL PROTECTED]
> http://free.prohosting.com/~maqua/
>
>
------------------------------
From: "Jeffery Nelson" <[EMAIL PROTECTED]>
Subject: With all the talk about random...
Date: Wed, 28 Jul 1999 09:26:19 -0000
What's so bad about C++ or (The dreader, but still valad) BASIC functions
for generateing random numbers. Are their methods flawed? I know they
derive them from a list and the time of day, but this seems random ENOUGH to
not be able to recognise a patruen. I was useing random keys in MY one time
pad generated by C++. Should I reconsider?
-Jeff
------------------------------
From: Albin Zuccato <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,alt.privacy,alt.security.keydist
Subject: Re: hush mail
Date: Wed, 28 Jul 1999 16:49:37 +0200
Anton Stiglic wrote:
> fungus wrote:
>
> > Anton Stiglic wrote:
> > > 128 bit is equivalent to 16 ASCII caracters, it's a bit better then an
> > > 8 ASCII caracter password on UNIX, but still....
> >
> > In what way a "bit better"???
> >
> > I'd say that squaring the attack time is more than "a bit better".
>
> Yes, you are correct, brute force attack on the passwords would be most
> likely impossible for
> the time beeing (sorry for any confusion, always happy to see how posters jump
> on someone if
> say something wrong ;). But brute force attack on the passwords is not the
> solution here,
> the initial secret is a passphrase, wich is transformed into a password, wich
> is hashed
> to something we will call h. Finaly, a _part_ of h is taken for
> validation. The hash
> function used is SHA, wich produces a 160 bit message digest. I don't know
> how
> big a part of that they take, depending on the size they take, brute force on
> that could
> (or could not) be directly applied.
>
> There may also exist other loop holes, using this technic, wich can be broken
> with something
> more intelligent than brute force.
>
> Anton
I think their is a little misunderstanding in the process.
They generate from your passphrase via a hash algorithmen (SHA 1 - is secure) a
128 bit key for Blowfish (is weak). This means that there is a wide distribution
of posible keys. For the reason that only 128 of the 160 (result of SHA1) are need
I could imagine that rest (160 - 128) is requested for identifying purpose.
An other solution is normally to make a lexical attack against a password. But
this is very hard here (because of the hash). You cannot identify a "good" result
so this is very hard to apply.
regards
Albin
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: What the hell is XOR?
Date: Wed, 28 Jul 1999 15:12:59 GMT
[EMAIL PROTECTED] wrote, in part:
>0 0 1 0 GT (NIMP is like NXOR; meaningful but rude)
Well, that will work in APL, where TRUE _is_ 1 and FALSE _is_ 0.
And you probably did come closer to what the fellow was thinking of.
But, of course, I would quibble that TRUE and FALSE aren't numbers;
they aren't even letters with alphabetical/lexicographical order, and
so there is no "standard" way recognized in mathematics in which the
operator > is applied to Boolean quantities.
And, of course, in Microsoft BASIC, FALSE is still 0, but TRUE is -1.
(Allowing bitwise operators to do Boolean logic as well.)
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Glenn Davis <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Wed, 28 Jul 1999 08:50:44 -1000
kctang wrote:
>
> Dear all,
>
> Please factorize the 80-digits number:
>
> 256261430091697968103677033465028955910<continue at next line>
> 15360341017076023809547878443033203276429
>
> Thanks & Bye, kctang
There are 3 factors
74681239503223976540012391
73935890729093478299508777
10094892705484334775926633
This was factored with the Quadratic Field Seive using
a pocket calculator in 163 minutes. The program is
available for $199.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: With all the talk about random...
Date: Wed, 28 Jul 1999 15:07:19 GMT
"Jeffery Nelson" <[EMAIL PROTECTED]> wrote, in part:
>What's so bad about C++ or (The dreader, but still valad) BASIC functions
>for generateing random numbers. Are their methods flawed? I know they
>derive them from a list and the time of day, but this seems random ENOUGH to
>not be able to recognise a patruen.
The methods are good enough for some purposes, but because they're
linear, a pattern can be easily recognized if you know what to look
for.
>I was useing random keys in MY one time
>pad generated by C++. Should I reconsider?
Yes. And you shouldn't call it a one-time pad if *any* algorithm, even
a good one that does produce a cryptosecure keystream suitable for a
stream cipher, is used to generate _pseudo_-random numbers for it.
Real random numbers are produced by rolling dice or equivalent
methods.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Wed, 28 Jul 1999 10:54:42 -0400
jd_bertron wrote:
> Has someone found a reduction of another NP-Complete problem to
> breaking RSA ?
No, it is not NP-Complete. In fact, there is no crypto-system that is
based on
an NP-Complete problem. Factoring, for example, is a problem that is
in a class a "little
under" NP-Complete (I forgot the name, sorry), and above P of cours
(there might be
other ways to break RSA than factoring, but that would just make RSA an
"easier"
problemt). There is an article, in a recent Crypto or Eurocrypt,
improving on earlier
results, that discusses this problem (there is something about the
hierarchy collapsing
if a cryptosystem problem would be NP-Complete).
I'll try to get info on the exact references....
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Standard Hash usage
Date: Wed, 28 Jul 1999 12:03:51 -0400
[EMAIL PROTECTED] wrote:
> > Rather than digging a deeper hole, I'll wait to see if
> > anyone else can find a definitive reference for how to construct
> > a 320-bit hash function from a 160-bit hash.
>
> Easy if your message has >= 320 bits of information just hash each
> half. You now have two 160bit hashes. You must note that normally the
> hash standards assume that the message will be about 512 bits, although
> they should be secure with smaller blocks.
This is not secure, for example, if you have a text of the form
header || Rest,
where header is always the same (say > 320 bits), you wil get info you
are not supposed to get after hashing it the way that was suggest above
(the
first halfis always stays the same). What Tom suggests in a latter post
is much
better.
Anton
------------------------------
From: John Xiao <[EMAIL PROTECTED]>
Subject: decode base64
Date: Wed, 28 Jul 1999 10:29:51 -0500
hey, guys
how can I decode a base64 file (certificate)?
thanks
------------------------------
From: "Digital" <[EMAIL PROTECTED]>
Subject: Anyone knows where to get original encryption source code?
Date: Thu, 29 Jul 1999 00:01:10 +0800
Hi,
I'm undergoing a project of analyising cryptography, does anyone knows where
can I get the generic codes of different encryption method like DES,
Blowfish, IDEA and many others?
Or does anyone knows of any encryption programs that uses generic methods of
encryption?
Thank you very much for your help! :)
P/S: My email is at: [EMAIL PROTECTED]
Regards,
Norman
------------------------------
From: "Digital" <[EMAIL PROTECTED]>
Subject: Anyone knows where to get original encryption source code?
Date: Thu, 29 Jul 1999 00:01:10 +0800
Hi,
I'm undergoing a project of analyising cryptography, does anyone knows where
can I get the generic codes of different encryption method like DES,
Blowfish, IDEA and many others?
Or does anyone knows of any encryption programs that uses generic methods of
encryption?
Thank you very much for your help! :)
P/S: My email is at: [EMAIL PROTECTED]
Regards,
Norman
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Wed, 28 Jul 1999 09:35:48 -0700
Glenn Davis wrote:
>
> kctang wrote:
> > Please factorize the 80-digits number:
> >
> > 256261430091697968103677033465028955910<continue at next line>
> > 15360341017076023809547878443033203276429
> >
> > Thanks & Bye, kctang
>
> There are 3 factors
>
> 74681239503223976540012391
> 73935890729093478299508777
> 10094892705484334775926633
>
> This was factored with the Quadratic Field Seive using
> a pocket calculator in 163 minutes. The program is
> available for $199.
Better check the precision on your calculator -- the product
of those three ends in a "1". They're also each composite
with small factors, unlike the target. Or was that humor?
kctang: Why do you want the factorization of this number?
--
Jim Gillogly
Sterday, 5 Wedmath S.R. 1999, 16:31
12.19.6.7.3, 8 Akbal 11 Xul, Eighth Lord of Night
------------------------------
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
From: Roger Carbol <[EMAIL PROTECTED]>
Date: Wed, 28 Jul 1999 15:26:49 GMT
kctang <[EMAIL PROTECTED]> wrote:
> Please factorize the 80-digits number:
> 256261430091697968103677033465028955910<continue at next line>
> 15360341017076023809547878443033203276429
1 and
256261430091697968103677033465028955910<continue at next line>
15360341017076023809547878443033203276429
.. Roger Carbol .. [EMAIL PROTECTED]
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: the defintion of Entropy
Date: Wed, 28 Jul 1999 13:06:54 -0400
I have seen some bad usage of the word entropy, so I taught I'd post the
definition.
There is two ways of considering entropy, one is mathematical (through a
set of axioms), the other is intuitive, I present the last one here:
Consider a source S that spits out bits, S -> 1 0 0 1 0 1 0 1 1
One intersting problem is to caracterize the output.
Say that the probability of outputs are p_0 = Pr(0) and p_1 = Pr(1).
We would like to know the uncertinty about the output of the source
S, that is, the entropy of S.
The entropy of S can be considered as "the average lenght, in bits,
needed to represent the output (a bit) of S".
In other words, if S spits outputs with probability p_0, p_1, then
the entropy of S (H(S)) is
H(S) = H(p_0, p_1) = p_0 *lg_2 (1/p_0) + p_1*lg_2(1/p_1)
Entropy can be generalized to a source that spits out elements of
a different base. Say S spits outputs with prob p_0, p_1, p_2, ...,
p_n,
then the entropy of S is
H(S) = H(p_0, p_1, ..., p_n) = sum(i=1; i<=n; i++) p_i*lg_2(1/p_i)
numbered examples:
S_0 -> 0000000... (S_0 outputs a constant)
then p_0 = 1 and p_1 = 0 and we have H(S_0) = 0;
S_ur -> 10010110 (S_ur outputs a bit choosen uniformatly randomly
then p_0 = 1/2 and p_1 = 1/2 and we have H(S_ur) = 1;
Anton.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Standard Hash usage
Date: Wed, 28 Jul 1999 12:36:50 -0400
David Wagner wrote:
Because it's not. In a moment of weakness I presumed that
sha1(x) == sha1(y) implied sha1(x||z) == sha1(y||z). Oops.
>
> Actually, I think your last remark is not so far off.
>
> At least in the case where x and y have the same length,
> and where that length is also a multiple of 512 bits,
> the statement holds with high probability, I believe.
>
> [Why? If the collision arises because of an internal
> collision in the internal chaining value, before the padding
> is processed, then indeed sha1(x||z) = sha1(y||z), as is
> easy to check.]
>
> Am I mistaken?
I'm not so sure that is true. If we say that SH1 has strong collision resitence
(i.e. it's "hard" to find any x, y, such that SH1(x) = SH1(y) )
then there might be a contradiction. If you say that sha1(x) == sha1(y)
implies sha1(x||z) == sha1(y||z) with high probability, that would mean
that founding the x and y such that sha1(x) == sha1(y) gives you a BUNCH
of collisions, just by taking any z' and trying out if sha1(x||z`) = sha1(y||z`).
I tried convincing myself doing the calculations on paper but haven't succeded
and I don't have much time do try (even do it's an interesting problem!).
Anton
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Wed, 28 Jul 1999 17:45:14 GMT
In article <[EMAIL PROTECTED]>,
kctang <[EMAIL PROTECTED]> wrote:
> Dear all,
>
> Please factorize the 80-digits number:
>
> 256261430091697968103677033465028955910<continue at next line>
> 15360341017076023809547878443033203276429
Why? Before I do it, I would like a reason. What is special
about this number?
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Vincent" <[EMAIL PROTECTED]>
Subject: Prime numbers wanted
Date: Wed, 28 Jul 1999 18:40:04 +0100
Hello guys and girls,
Here is my "problem" :
Is there any faster algorithm than the following one, which, given an (odd)
number n, returns the first prime number p>=n ?
Assuming that I have a function is_prime tellimg me if a number is (or has
enough odd to be) prime (The Miller-Rabin test).
int My_Simple_Algorithm (int n)
{
int temp=n;
while (!is_prime(temp)) temp+=2;
return(temp);
}
Thank you for your help, I really got to make this working faster than this
algorithm actually does.
====================================================
Vini boy
[EMAIL PROTECTED]
------------------------------
From: Jim Geary <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Wed, 28 Jul 1999 10:35:40 -0700
A cursory inspection reveals your second number is evenly
divisible by (at least) three. Perhaps your reply was a
joke that I failed to get.
Jim Geary
jaygee at primenet dot com
http://www.primenet.com/~jaygee/
On Wed, 28 Jul 1999, Glenn Davis wrote:
> kctang wrote:
> >
> > Dear all,
> >
> > Please factorize the 80-digits number:
> >
> > 256261430091697968103677033465028955910<continue at next line>
> > 15360341017076023809547878443033203276429
> >
> > Thanks & Bye, kctang
>
> There are 3 factors
>
> 74681239503223976540012391
> 73935890729093478299508777
> 10094892705484334775926633
>
> This was factored with the Quadratic Field Seive using
> a pocket calculator in 163 minutes. The program is
> available for $199.
>
>
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Wed, 28 Jul 1999 11:27:25 -0700
Bob Silverman <[EMAIL PROTECTED]> wrote in message
news:7nnfj8$6uo$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> kctang <[EMAIL PROTECTED]> wrote:
> > Dear all,
> >
> > Please factorize the 80-digits number:
> >
> > 256261430091697968103677033465028955910<continue at next line>
> > 15360341017076023809547878443033203276429
>
> Why? Before I do it, I would like a reason. What is special
> about this number?
I hope this does not turn into one of those silly "this number is special
because" contests.
It is not prime.
None of the easy factoring algorithms works. It will require quadratic
sieve, ECPP or the like and take quite a while.
--
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: Bob Silverman <[EMAIL PROTECTED]>
Crossposted-To: sci.math.symbolic
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Wed, 28 Jul 1999 17:49:35 GMT
In article <[EMAIL PROTECTED]>,
kctang <[EMAIL PROTECTED]> wrote:
> "Richard B. Kreckel" wrote:
>
> > If this is supposed to be a game you forgot to tell us what we can
>>win if we factorize that number.
> possesses the command "factor". But such computer algebra systems are
> usually slow.
Because they do not implement fast integer factorization algorithms.
Such algorithms are rather specialized.
>
> I want to know . . . . which system, amount of time to factor . . . .
.
> Techniques of generating hard to factor integers .....
Hard to factor integers??? Generate two large primes. Multiply them.
Time to factor an 80 digit number? About 15 to 20 hours on my Pentium
II 450 using MPQS.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Tue, 27 Jul 1999 15:08:08 -0400
From: [EMAIL PROTECTED]
Subject: Re: With all the talk about random...
Jeffery Nelson wrote:
>
> What's so bad about C++ or (The dreader, but still valad) BASIC functions
> for generateing random numbers. Are their methods flawed? I know they
> derive them from a list and the time of day, but this seems random ENOUGH to
> not be able to recognise a patruen.
How hard did you look? I know of no C++ compiler with a
cryptographically adequate rand() function.
I was useing random keys in MY one time
> pad generated by C++. Should I reconsider?
Yes.
------------------------------
** 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
******************************
