Cryptography-Digest Digest #57, Volume #13 Tue, 31 Oct 00 13:13:01 EST
Contents:
Hieratic Number System ([EMAIL PROTECTED])
Hieratic Number System ([EMAIL PROTECTED])
Re: RSA Multiprime (JCA)
Re: Newbie about Rijndael (SCOTT19U.ZIP_GUY)
Re: A new paper claiming P=NP (Timothy Chow)
Re: Is RSA provably secure under some conditions? (David A Molnar)
Re: 3-dimensional Playfair? ("Tony T. Warnock")
Re: Q. to Ritter /PKCS cascade/Hybrid PKCS (JPeschel)
Re: RSA Cryptography Today FAQ (1/1) ("Jakob Jonsson")
Re: RSA Multiprime (Bob Silverman)
Re: RSA Multiprime (Bob Silverman)
Re: End to end encryption in GSM (Mark Currie)
Re: Legal reqiurements for CCTV watermarking ("Trevor L. Jackson, III")
Re: ciphertext smaller than blocksize (James Felling)
Re: XOR based key exchange protocol - flawed? (David Wagner)
Re: BEST BIJECTIVE RIJNDAEL YET? (James Felling)
Re: XOR based key exchange protocol - flawed? (David Wagner)
Re: Arbitrated signature scheme (conventional cryptosystem) (David Wagner)
Re: Open Request to Dr. Kaliski, Jr. at RSA Research - looking for your (David
Wagner)
Re: RSA Multiprime (Francois Grieu)
Re: Is RSA provably secure under some conditions? (David Wagner)
Re: Hieratic Number System ([EMAIL PROTECTED])
Re: RSA Multiprime (Francois Grieu)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Hieratic Number System
Date: Tue, 31 Oct 2000 14:50:28 GMT
I am doing a project for school on the Hieratic Number System. I have
found the symbols for the numbers 1 through 6 but I am looking for 7
through 10, 100, 1,000, 100,000 and 1,000,000. Can you help me find
these symbols? My project is due on Thursday, Nov. 2. Thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Hieratic Number System
Date: Tue, 31 Oct 2000 14:52:11 GMT
I am doing a project for school on the Hieratic Number System. I have
found the symbols for the numbers 1 through 6 but I am looking for 7
through 10, 100, 1,000, 100,000 and 1,000,000. Can you help me find
these symbols? My project is due on Thursday, Nov. 2. Thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: RSA Multiprime
Date: Tue, 31 Oct 2000 06:59:19 -0800
Scott Contini wrote:
> In article <[EMAIL PROTECTED]>,
> JCA <[EMAIL PROTECTED]> wrote:
> >
> > While a neat thing, I am not all that fond of multiprime moduli. But
> >that's just me.
> >
>
> A neat thing? Are you kidding me?
I was just trying to be polite. As you could infer from my posting,
I am not enamoured with this technique.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Newbie about Rijndael
Date: 31 Oct 2000 15:00:15 GMT
[EMAIL PROTECTED] (mac) wrote in <8tmb13$jmm$[EMAIL PROTECTED]>:
>Thanks for reply.
>
>This seems like a very good idea, but it makes me concerned about
>compatibility with other encryption applications using Rijndael. My main
>goal is to make an ActiveX component which implements Rijndael
>encryption for encrypting/decrypting both strings and whole files. Matt
>Timermanns code and idea are great but we loose compatibility.
>
I am not sure what the compatability features are with
ActiveX I am not up on it. But having worked on various
systems for the government many year I would guess there is a
way round it. Since you could use Matts code to do the actual
encryption then just pretend the string of data that results
is normal data and then do some other standard implementation of
top as if it was just normal data. These are quick thoughts
and like I said I have not done any ActiveX but just think a little.
>
>"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>>
>> Try Matt Timermanns code it will handle 2 bytes fine
>> http://www3.sympatico.ca/mtimmerm/bicom/bicom.html
>>
>> David A. Scott
>> --
>> SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
>> http://www.jim.com/jamesd/Kong/scott19u.zip
>> Scott famous encryption website **now all allowed**
>> http://members.xoom.com/ecil/index.htm
>> Scott LATEST UPDATED source for scott*u.zip
>> http://radiusnet.net/crypto/ then look for
>> sub directory scott after pressing CRYPTO
>> Scott famous Compression Page
>> http://members.xoom.com/ecil/compress.htm
>> **NOTE EMAIL address is for SPAMERS***
>> I leave you with this final thought from President Bill Clinton:
>
>
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
From: [EMAIL PROTECTED] (Timothy Chow)
Date: Tue, 31 Oct 2000 15:27:54 GMT
In article <[EMAIL PROTECTED]>,
Peter Fairbrother <[EMAIL PROTECTED]> wrote:
>The people supposedly giving the prize made a not-quite-trivial mistake
>regarding Poincare's Conjecture on their site.
What is this mistake?
>I clicked on a link. Desn't give me confidence.
That's bad. I believe that the prize is legit, though; I went to the
opening ceremonies of the CMI and there were lots of famous people there.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: 31 Oct 2000 15:16:19 GMT
John A. Malley <[EMAIL PROTECTED]> wrote:
> Yes, some notions of "provable security" are subject to change. Check
> out "The Random Oracle Methodology, Revisited" by Ran Canetti, Oded
> Goldreich and Shai Halevi, dated October 11, 2000 at the LANL on-line
> archive but originally appeared in the Proceedings of 30th Annual ACM
> Symposium on the Theory of Computing, pages 209-218, May 1998, ACM:
In fairness, I think that people were uncomfortable with random oracles
even before this paper. At least the papers which use the model are always
making the disclaimer "well, this doesn't say anything about the real
world, but hey, maybe it's a good heuristic."
but yes, this is a very weird and wonderful result.
> this scheme. Evaluating schemes with the Random Oracle Model rules out
> some, but not all, insecure schemes.
> Made my jaw drop.
Yes!
> Gosh, the math in the paper itself made my jaw drop. Still reading it,
> do not yet completely understand their proofs but I'm working on it.
The key idea seems to be that nasty little self-referencing relation
R(x,y) = 1 if x = description of H, y = H(description of H). Actually,
any relation which you knew was fixed in advance and held of all
static functions would work, although I can't think of any others off the
top of my head. This relation exploits the fact that any possible
implementation of the random oracle must be a static object.
It's actually close in spirit to Turing's proof about the undecidability
of the Halting Problem. At least, that's how I think of it.
Then the rest of the paper is extending the proof idea...
-David
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: 3-dimensional Playfair?
Date: Tue, 31 Oct 2000 08:31:52 -0700
Reply-To: [EMAIL PROTECTED]
A pocket calculator cypher would be interesting. Playfair is easy to
implement. One needs a simple transformation based on a key and some
numerical and logical transforms. If a program is used, it must be
simple and entered in anew each invocation.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Q. to Ritter /PKCS cascade/Hybrid PKCS
Date: 31 Oct 2000 15:34:46 GMT
Mike Connell [EMAIL PROTECTED] writes:
>[EMAIL PROTECTED] (JPeschel) writes:
>
>> Mok-Kong Shen [EMAIL PROTECTED] writes:
>>
>> >If you publish, then you'll get fame and become a guru
>> >or even be immortal (possible in France).
>>
>> It's tough to become immortal by publishing your work.
>> I plan to become immortal by not dying. Only one
>> slight bug to work out.
>>
>
>How to stop the ghost of Woody Allen from haunting you? ;-)
>
Sheesh; make that two bugs...
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.ripem
Subject: Re: RSA Cryptography Today FAQ (1/1)
Date: Tue, 31 Oct 2000 16:34:54 +0100
Unfortunately, the three-year-old message below is since long obsolete and
contains incorrect information; in vain, we have sent requests to
[EMAIL PROTECTED] asking them to remove it. The correct URL is
http://www.rsasecurity.com/rsalabs/faq/
and the correct address to the FAQ editor is
[EMAIL PROTECTED]
By the way, the RSA Labs FAQ should not be confused with the sci.crypt FAQ,
which is an entirely different document.
Jakob Jonsson
RSA Laboratories
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote in message
<[EMAIL PROTECTED]>...
> Originator: [EMAIL PROTECTED]
> Date: 30 Oct 2000 14:26:41 GMT
> Lines: 19
> NNTP-Posting-Host: penguin-lust.mit.edu
> X-Trace: dreaderd 972916001 5721 18.181.0.29
> Xref: xlerb.dynas.se sci.crypt:151019 alt.security.ripem:2332
>
> Archive-name: cryptography-faq/rsa/part1
> Last-modified: 1997/05/21
>
>
> An old version of the RSA Labs' publication "Answers to Frequently Asked
> Questions about Today's Cryptography" used to be posted here until May
> 1997. These postings were not sponsored or updated by RSA Labs, and
> for some time we were unable to stop them. While we hope the information
> in our FAQ is useful, the version that was being posted here was quite
> outdated. The latest version of the FAQ is more complete and up-to-date.
>
> Unfortunately, our FAQ is no longer available in ASCII due to its
> mathematical content. Please visit our website at
> http://www.rsa.com/rsalabs/ to view the new version of the FAQ with your
> browser or download it in the Adobe Acrobat (.pdf) format.
>
> RSA Labs FAQ Editor
> [EMAIL PROTECTED]
>
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: RSA Multiprime
Date: Tue, 31 Oct 2000 15:44:44 GMT
In article <[EMAIL PROTECTED]>,
Francois Grieu <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Scott Contini) wrote:
> > The only thing more ridiculous than Compaq patenting this is
> > RSA Security licensing the patent.
>
> Agreed, if true. I have not seen the patent claims, and do not
> know the details of the cross-licensing agreements between Compaq
> and RSA Security. I hope scientists still have some influence at
> RSA security (Bob are you listening ?). I bet the net flow of cash
> from Compaq to RSA Security will be remain non-negative.
I am not involved in marketing decisions of the company.
> Well, GNFS and even MPQS are faster than ECM for pratical purpose,
You are comparing different things. ECM's run time depends on the
size of the factors. Let N = 17*p where p is 1000 bits. ECM
will succeed instantly, whereas factoring N by GNFS or MPQS is beyond
the state of the art.
> and all three are equaly efficient against two-prime and
> multi-prime RSA. The product of 2 random 288 bit primes is just
> as hard to factor as the product of 3 random 192 primes, and this
> situation has not evolved in the last 20 years.
Finding a 192-bit prime with ECM will be a little easier than
factoring a 576-bit number with GNFS.
--
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/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: RSA Multiprime
Date: Tue, 31 Oct 2000 15:50:44 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
> The original RSA patent that just expired mentioned the possibility
of using
> more than 2 primes. Draw your own conclusions about the Compaq
multiprime
> patent. Bob Silverman, RSA Labs, at the last ANSI X9F1 meeting said
he thought
> the Compaq patent would be declared invalid.
I said no such thing. I did NOT say that it *would* be invalidated,
I said that it *could* be easily challenged. Because of the way our
laws work, one can't just go into court and say "I challenge this
patent". One must VIOLATE the patent, then have the owner sue you over
the violation. It is a protracted and messy and expensive process.
Any challenge is almost certain to succeed. But one must weigh the cost
of the challenge against the cost of licensing fees. This is true all
the time. Many patents are easier to accede to than to fight.
--
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/
Before you buy.
------------------------------
Crossposted-To: nl.comp.crypt,alt.comp.opensource,alt.cellular.gsm
Subject: Re: End to end encryption in GSM
From: [EMAIL PROTECTED] (Mark Currie)
Date: 31 Oct 2000 16:06:34 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>> I'm not sure what you mean. How can the data rate limit the strength of the
>> encryption scheme ?
>
>If you encrypt something the output size is proportional to the size of
>the key and usually the longer the key the more difficult to break the
>encryption. But of course I'm not an expert.
I am still a bit confused. I think what you may be refering to is that if you
use a block cipher the output block size is "typically" proportional to the key
size. Usually crypto phones that encrypt compressed digital speech use stream
ciphers. In this case you do not get data expansion. Also, you can use the
cipher in cipher-feedback mode. This allows the cipher to automatically
re-synchronise on errors. It does have the unfortunate property of propagating
the error bits to (typically) the length of the key. however, in practise
errors occur in bursts, and the additional error propagation does not affect
the quality significantly.
You can also convert a strong block cipher to a stream cipher and configure
it operate in cipher feedback mode (bit-by-bit feedback). Bit feedback is
important because of bit-slip or bit-gain errors. A byte feedback system will
lose synch in this case.
Mark
------------------------------
Date: Tue, 31 Oct 2000 11:27:49 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Legal reqiurements for CCTV watermarking
Andrew Cogger wrote:
> Greetings.....
>
> (Appologies if this is way way way OT)
>
> I am investigating the technical aspects of watermarking for a CCTV
> system currently under development. Video storage is digital, on
> HDD's. The customer states that the digital images must be
> watermarked in such a way as to guarrantee their integrity in
> order to be classed as 'admissable evidence in a court of law'.
>
> My question...does anyone have any idea what the requirements
> for digital watermarks/signatures are in order for them to be
> used in court? I realise that this is locale specific, but any legal
> precedents or examples would be greatly appreciated.
Typically the trust of a disinterested third party is used to prevent
after-the-fact forgeries. This can be as simple as generating hash
values for the protected data and recording those values with a third
party or publishing them in a forum of record. The hashes are usually
chained so that forging a value would invalidate all subsequent values.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: ciphertext smaller than blocksize
Date: Tue, 31 Oct 2000 11:22:29 -0600
"SCOTT19U.ZIP_GUY" wrote:
> [EMAIL PROTECTED] wrote in <8tl1c9$fkv$[EMAIL PROTECTED]>:
>
> >[snip my statement that the entropy of the key is diffused into the
> >plaintext in the creation of the ciphertext]
>
> Actually the word entropy not in your previous message so your
> lying plain and simple.
>
> Entropy is more a funtion of the possible message density.
> If its one per bit then you have maximum entropy in the shanon
> sense. I am not sure where your trying to take this.
> But if I have a one bit key. where I multipy by 1 or -1. I still
> would not say I physically added information to the file.
I would. The entrophy added is miniscule though. ( bad algorithim as
the sign swithch is effectively sending cleartext if key=1, and sending
slightly obscured data if key = -1. ( reading as char will definitely be
impaired). OTOH , If your key is which direction you rotate, and you
encode by rotating the message 1 bit in the chosen direction , then it
becomes obvious that some entrophy has been added as 50% of the time you
will have guessed the wrong key, and have to rotate it the other way.
>
>
> David A. Scott
> --
> SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
> http://www.jim.com/jamesd/Kong/scott19u.zip
> Scott famous encryption website **now all allowed**
> http://members.xoom.com/ecil/index.htm
> Scott LATEST UPDATED source for scott*u.zip
> http://radiusnet.net/crypto/ then look for
> sub directory scott after pressing CRYPTO
> Scott famous Compression Page
> http://members.xoom.com/ecil/compress.htm
> **NOTE EMAIL address is for SPAMERS***
> I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: XOR based key exchange protocol - flawed?
Date: 31 Oct 2000 17:26:55 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
David Schwartz wrote:
>A knows it's talking to mb, which it thinks is B.
There's where you're wrong. A knows it is talking to mb, which
it thinks is mb! No problem here.
A has no reason to think it is talking to B, and it is unreasonable
to interpret the protocol as saying that A should conclude it is
talking to B even when it has received the public key Pmb and not
Pb. The name of B has never even been mentioned in the conversation
with A.
I suspect you're confused about the goals of an authentication protocol.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: BEST BIJECTIVE RIJNDAEL YET?
Date: Tue, 31 Oct 2000 11:31:24 -0600
"SCOTT19U.ZIP_GUY" wrote:
> [EMAIL PROTECTED] (Brian Gladman) wrote in
> <kmkL5.4161$zO3.132848@stones>:
>
> >
> >"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> >> [EMAIL PROTECTED] (Brian Gladman) wrote in
> >> <XUhL5.4086$zO3.128477@stones>:
> >>
> >> >I certainly did not claim that the length is 'added' to the file -
> >> >what I said was that it was encoded in the file, which is quite
> >> >different. Moreover, while the encoding adds no _data_ , it certainly
> >> >adds _information_ since the file length could not be recovered if it
> >> >did not.
> >> >
> >> > Brian Gladman
> >> >
> >>
> >> Your wrong the lemght info is not encoded in the file. You can
> >> change
> >> the bits in the file to anything you want and the lenght would not
> >> change. The length that the operating system allocates for the file is
> >> something different. The data encrypted is the file data. Nohting in
> >> that data has any need for a length encoding.
> >
> >There are two situations that are possible:
> >
> >(a) I can recover the exact original file from its compressed form and
> >then measure the length of the resulting file;
> >(b) I cannot accurately recover the original file and hence cannot
> >determine its length.
> >
> >If (a) applies I have an algorithm for determining the original file
> >length when given only a compressed version of the file so this
> >information must be encoded somewhere in the latter.
> >
> >If (b) applies then the compression scheme is lossy and I am no longer
> >interested in it
> >
> >So which is it - (a) or (b)?
> >
> > Brian Gladman
> >
> >
> >
> >
>
> From the constraint you out it in.It is like is light a wave or particle.
> Or have you stopped betting your wife. Or who cuts the babers hair when
> the barber only cuts those who don't cut there own hair.
>
> Here is a better realy world example. My bijective compression routine
> is the identiy transform. I am compressing one byte files. I compress
> each of the 256 possible files. I got 256 files out. where in any of
> these 256 files is the lenght encoded. No where! the operating system
> has allocted the lenght. I'm free to choose what;s in the files. If you
> can't see this your not intelligent to carry the conversation on and
> I am done since I don't think any one following this thread thanks
> you have a point at all.
In any compression scheme the message length is encoded.( it may not be encoded
as additional data however)
In your example the "compression routine" is length preserving. Therefor the
length of the original plaintext is exactly the length of the output. That
routine "embeds" length information in its output -- the length out =length in.
OTOH if my compression routine changes the length of the data it must encode
that information in some way within the file, either by a "stop" character, or
a "termination state" for the algorithim, or some form of embeded length
field.( this may be as simple as if you hit EOF then stop)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: XOR based key exchange protocol - flawed?
Date: 31 Oct 2000 17:31:48 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
David Schwartz wrote:
> The MITM can create any number of
>anonymous personas. So he can make you think that he is the person who
>gave you all those stock tips even though he isn't. The MITM can create
>a one-to-one mapping of his keys to the keys of people you communicate
>with. He can then later make you think that any subsequent message came
>from any of the poeple he has impersonated to you.
No, he can make you think that they came from his mirror key.
I think you're confused about the goals of an authentication protocol.
This so-called "problem" is common to _every_ authentication protocol
on the face of the earth.
But the real problem is not in the authentication protocol. The
problem is in a mis-interpretation of what an authentication protocol
really tells you.
Seeing a message signed by Alice's public key does _not_ mean that
Alice authored that message. It just means that Alice applied her
signature key to it. She could have taken a message signed by Bob,
stripped off Bob's signature, and appended her own.
In particular, have you ever heard of how to beat a grandmaster at
chess? The trick is to play _two_ grandmasters by postal chess;
you let one go first, and echo his move to the other grandmaster,
and then simply relay their moves back and forth. In essence, the
grandmasters are playing each other. This guarantees that you'll
win one game and lose the other (or, draw them both, anyway, which
is just as impressive against a grandmaster!).
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Arbitrated signature scheme (conventional cryptosystem)
Date: 31 Oct 2000 17:34:35 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Jan Fedak wrote:
>Here's what Selim G. Akl offers as an arbitrated signature scheme
[...]
>3. She computes $C = E_{k_{SA}}(m, h)$ and sends it along with
> UNENCRYPTED $M$ to arbiter.
[...]
>The enemy then knows $C$, $m$ and $h$ and can easily obtain $k_{SA}$.
How do you obtain $k_{SA}$? You know $(m,h)$ and $C$, so you
have a known plaintext/ciphertext pair for the cipher $E_{k_{SA}}$,
but how does this help? Ciphers are supposed to be secure against
known-plaintext attacks.
What am I missing?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Open Request to Dr. Kaliski, Jr. at RSA Research - looking for your
Date: 31 Oct 2000 17:36:50 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
John A. Malley wrote:
[... prng : G -> G is a group homomorphism, as is c : G -> G ...]
>Show there is an "analog" for the ciphertext-only attack on the output
>of a LCG encrypted with ElGamal (as outline in the draft paper) for the
>output of prng() enciphered by c() as defined on the group G?
I still don't understand what this should mean. A prng() takes a short
random seed and stretches it into a long output. Your prng() takes a
short seed and gives a same-size output, so you can only use it for
one signature. A scheme that can only be used to sign one message
is probably not too interesting. Did you mean something different?
I'm sure I must be misunderstanding.
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RSA Multiprime
Date: Tue, 31 Oct 2000 18:39:27 +0100
In article <8tmpdb$rol$[EMAIL PROTECTED]>, Bob Silverman
<[EMAIL PROTECTED]> wrote:
> You are comparing different things. ECM's run time depends on the
> size of the factors. Let N = 17*p where p is 1000 bits. ECM
> will succeed instantly, whereas factoring N by GNFS or MPQS is beyond
> the state of the art.
Thanks for the correction. I was indeed wrong saying ECM is equaly
efficient on 2 and 3 prime-factor numbers of equal size.
> Finding a 192-bit prime with ECM will be a little easier than
> factoring a 576-bit number with GNFS.
Maybe, but this must be close. According to
<http://www.loria.fr/~zimmerma/records/ecmnet.html>
the largest prime factor found with ECM for a moreless
general number is 177 bits, for an effort that probably was
below last years sucess for 512 bit using GNFS. This tells the
thresold (between ECM and GNFS for product of 3 random primes of n
bits) is over n = 177 bits, but how do we get to 192 bits ?
Francois Grieu
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Is RSA provably secure under some conditions?
Date: 31 Oct 2000 17:41:46 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
John A. Malley wrote:
>They show a most marvelous thing: There exist signature and encryption
>schemes that are secure in the Random Oracle Model but for which any
>_implementation_ of the random oracle results in insecure schemes. The
>fact that a scheme is secure in the Random Oracle Model cannot be taken
>as evidence or indication to the security of possible implementations of
>this scheme.
Yes, they show that there are examples of schemes that are secure under
the random oracle model but insecure in all real implementations.
However, their example is pretty artificial, and there are no known
natural examples of failures of the random oracle model.
The purist would say that if you don't have a full proof of security
(without any assumptions), you have nothing. But from a practical point
of view, I think this is too strong. After all, in cryptography we make
funny assumptions all the day long ("factoring is hard", "RSA is secure",
"the Diffie-Hellman decision problem is infeasible"), because we can't
prove any scheme secure without some unproven assumption.
So proofs of correctness in the random oracle model are just a heuristic
-- they are not an absolute guarantee of security -- but they are still,
IMHO, extremely useful. They provide powerful (though not absolute)
evidence that the scheme is very likely to be secure.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hieratic Number System
Date: Tue, 31 Oct 2000 17:36:07 GMT
In article <8tmm7h$omn$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I am doing a project for school on the Hieratic Number System. I have
> found the symbols for the numbers 1 through 6 but I am looking for 7
> through 10, 100, 1,000, 100,000 and 1,000,000. Can you help me find
> these symbols? My project is due on Thursday, Nov. 2. Thanks.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
See http://noisefactory.co.uk/research/sci-math/history/hist003.html
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RSA Multiprime
Date: Tue, 31 Oct 2000 18:52:28 +0100
In article <8tmpdb$rol$[EMAIL PROTECTED]>, Bob Silverman
<[EMAIL PROTECTED]> wrote:
> You are comparing different things. ECM's run time depends on the
> size of the factors. Let N = 17*p where p is 1000 bits. ECM
> will succeed instantly, whereas factoring N by GNFS or MPQS is beyond
> the state of the art.
Thanks for the correction. I was indeed wrong saying ECM is equaly
efficient on 2 and 3 prime-factor numbers of equal size.
> Finding a 192-bit prime with ECM will be a little easier than
> factoring a 576-bit number with GNFS.
Maybe, but this must be close. According to
<http://www.loria.fr/~zimmerma/records/top100.html>
the largest prime factor found with ECM for a moreless
general number is 179 bits, for an effort that probably was
below last year's sucess for 512 bit using GNFS. This tells the
thresold (between ECM and GNFS for product of 3 random primes of n
bits) is over n = 179 bits, but how do we get to 192 bits ?
Francois Grieu
[updated; my 177 bit record was for year 2000 only]
------------------------------
** 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
******************************
