Cryptography-Digest Digest #86, Volume #13 Fri, 3 Nov 00 14:13:00 EST
Contents:
Re: RSA vs. Rabin (Tom St Denis)
Re: Rijndael Security (Tom St Denis)
Re: Q: Computations in a Galois Field (Tom St Denis)
Microsoft's script encoder ("Lefty Louther")
Re: Really Strong Cipher Idea? (Mok-Kong Shen)
Re: Detectable pattern in encoded stegaanographic images (nemo outis)
Re: RSA Multiprime (Mok-Kong Shen)
Re: Psuedo-random number generator (Herman Rubin)
Re: RSA vs. Rabin (Francois Grieu)
Re: ECC choice of field and basis (Mike Rosing)
Re: Microsoft's script encoder (Tom St Denis)
Re: Q: Computations in a Galois Field (Mike Rosing)
Re: Crypto Export Restrictions ("Trevor L. Jackson, III")
Re: Microsoft's script encoder ("Lefty Louther")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RSA vs. Rabin
Date: Fri, 03 Nov 2000 16:59:30 GMT
In article <8tuiij$aj3$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> In article <8tsl7m$pu4$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > > Is this little difference the reason why Rabin is provably as
> > secure
> > > as factorization?
> >
> > Yes. If you can find square roots, i.e a^2 = b^2 mod N (a != b)
then
> > you can factor N. Thus solving the square root (well I think this
is
> > how the proof goes, of course Bob will correct me) is as difficult
as
> > factoring.
>
> Somewhat simplified, but essentially correct. But you also need
> a != -b mod N as well as a != b mod N
Yup, sorry for omitting that.
> >
> > The question remains: Is factoring hard?
> >
> > > 2. RSA with low exponents is found insecure today.
>
> Nope. Wrong. Thank you for playing.
> Please explain where you heard this and why you think your statement
> is correct.
I didn't say that, the OP did.
> > Rabin is insecure for various other reasons I would imagine.
>
> Oh? Please tell us why you think this, and what these other reasons
> might be. If you can't then you have no business making such a
> statement.
>
> R-W is subject to a known ciphertext attack which can reveal the key
> (and not just the plaintext or signature!). But correct padding
> destroys the attack.
Ahem. P407 of Knuth Vol2, The Art of Computer Programming, and I quote
"However, the system has a fatal flaw that does not seem to be present
in the RSA scheme (see exercise 33): Anyone with access to the SQRT
box can easily determine the factors of it's N."
I believe Knuth is referring to a SQRT box without random padding
however...
But that is my source of info on the subject.
> > RSA is more convenient as well. You can easily perform either
> > operation and you can do signatures, etc..
>
> Rabin-Williams with e = 2 is 50% faster than RSA with e = 3
> (and faster still than RSA with larger e) for verifying signatures.
> I therefore ask why you think RSA is "more convenient"?
Because the math is simpler and you only get one solution? I guess if
you're into commercial apps R-W is better, but I am not, and the OP is
probably not either.
> > RSA is conjectured to be as hard as taking the discrete logarithm
> > modulo a composite (and with sufficient twisting as hard as
> factoring).
> >
> > However, there is no proof that you need to factor to solve the RSA
> > problem. In the case of Rabin it has been proven that you need to
> > factor to take the square root.
>
> This is almost, but not quite correct. What would be correct is
> saying that finding square roots modulo a composite is polynomially
> equivalent to factor. You don't NEED to factor to take the square
> root. You could find the square root by direct search without
> factoring. However, once you have done so, you can factor the modulus
> easily.
Yup, I stand (or sit) correct.
Thanks for the help,
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Rijndael Security
Date: Fri, 03 Nov 2000 17:03:43 GMT
In article <3a028dcf$[EMAIL PROTECTED]>,
"ajd" <[EMAIL PROTECTED]> wrote:
>
> How secure is Rijndael when given (most of) the plaintext and the
cipher
> text? For example if I encrypt a bitmap (and somehow the
interceptor
> knows its a bitmap), the interceptor then knows that the first block
will
> decrypt to
>
> 42 4D ** ** ** ** 00 00 00 00 36 00 00 00 28 00
>
> where bytes 0-1 are the bitmap identifier
> 2-5 are the file size (which the interceptor doesn't *quite* know as
my
> encrypted file will be a multiple of the block size, and vthe
plaintext file
> may not be)
> 6-9 reserved and always zero
> 10-13 is the offset to beginning of bitmap data
> 14-17 is th header size
>
> Given this information about the plaintext, and given the encrypted
text,
> can the interceptor work out the key? It seems to me like we are
giving away
> a bit too much information. Is there a standard to get around this
problem?
When Rijndael is implemented and use correctly there is no known short-
cut attack to find the key. Regardless of the amount of known blocks.
I say "used correctly" as in a good source of entropy for the key, a
good chaining method (CBC, ABC, etc...) and good destruction of the
memory once it's been used. (i.e don't leave the key in memory...)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Fri, 03 Nov 2000 17:00:53 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > > Dumb question: For GF(2^m) with m sufficiently large, are
> > > there specific tricks in programming that could speed up
> > > multiplication/division? Thanks.
> >
> > I believe you meant GF(2)^m as in a polynomial basis with binary
> > components. I keep getting mixed up with this as well (although
people
> > have explained it...)
>
> No. I mean exactly GF(2^m), the finite field of order 2^m
> (a Galois field that is known to exist). I don't know
> the mathematical object you referred to or its relationship
> to GF(2^m).
Um, cuz GF(p) is known as "a finite field with a prime p as a
modulus". GF(2)^n refers to polynomials of degree 'n' with
coefficients in GF(2).
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Lefty Louther" <[EMAIL PROTECTED]>
Subject: Microsoft's script encoder
Date: Fri, 3 Nov 2000 19:15:35 +0200
When i use microsoft's script encoder (screnc.exe) for
string :
response.write ("lakis")
I get :
#@~^IAAAAA==@#@&DnkwKx/?RS.kD+~`rVCVb/J*@#@&vwgAAA==^#~@
Does anyone know what kind of cipher algorithm is it ?
Thank you,
Lefty
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Really Strong Cipher Idea?
Date: Fri, 03 Nov 2000 18:18:24 +0100
John Savard wrote:
>
> So in leaving the one-time-pad, I can only judge my security by a
> subjective impression that the cipher I am using seems very
> complicated, and the only objective fact I have is that it wasn't
> broken _yet_.
I think that it could be said that the art of designing a
good cipher is to obtain much 'complexity' for the opponent
using however mechanisms that are sufficiently simple
in order to avoid illusions and bugs and other undesirable
things from happening. Rijndael is a very good example of
this in my humble view.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (nemo outis)
Subject: Re: Detectable pattern in encoded stegaanographic images
Date: Fri, 03 Nov 2000 17:27:08 GMT
Your points are well taken. However, I do have one small cavil about
"steganographic methods are only useful in cases where their use are not being
suspected." While this is the usual case, steganography can still have value
even if its use is suspected (but not known/provable for sure). This might be
the situation if use of encryption is illegal or if one can be legally coerced
(perhaps under pain of contempt) to decrypt a file. Steganography would
give one "plausible deniability" that one is using encryption. One could, for
instance, maintain that the low order bits in one's .wav file are noise, not
encryption. The situation is not entirely hypothetical; arguably it's the
way things are in the UK right now with the RIP law.
So the question of a pattern in stego files is relevant not only to detection
but also as a method of proving that encryption has been used.
Regards,
In article <bhyM5.13648$[EMAIL PROTECTED]>, "Peter
Thorsteinson" <[EMAIL PROTECTED]> wrote:
>> This is a fairly obvious failure to understand stego. The purpose of
>> steganography is to hide a seperate message inside another message
>> (encrypted text inside a bmp in this case). If you have access to the
>> unaltered original, of course you can detect the presence of either
>> corruption or steganography. The point comes from the fact that your
>> assumed attacker does not have access to the cover message without the
>> stego (the original bmp in this case). Hope this helps.
>
>He didn't just say that he could detect a difference (duh). He said he
>"found a very clear pattern" that showed up when he compared them. I guess
>the question is "what is the pattern". If it is indeed a pattern, then
>perhaps it could be leveraged to detect steganographic usage. That would be
>cool, because the steganographic methods are only useful in cases where
>their use are not being suspected.
>
>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: RSA Multiprime
Date: Fri, 03 Nov 2000 18:28:03 +0100
Francois Grieu wrote:
>
> [EMAIL PROTECTED] (Tony L. Svanstrom) wrote:
>
> > Bob Silverman wrote:
> > > Because of the way our (US) 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.
> > >
> > Is it like that with all patents, that once the public finds out about
> > them the are already set in stone and you need to get sued to be able
> > to challenge it? I have a hard time believing that, it simply sounds
> > too stupid to be true.
>
> In Europe, a patent can be challenged even if the patentholder is not
> willing to sue. It sometime happens, but the problem is: who wants to
> bear the cost of challenging a patent if not using the technique
> described and beeing asked money for it by the patentholder ?
> So it often gets back to the US situation.
>
> The cases of challenged patent tend to fall into one of five categories:
> - the patentholder is engaged in the process of suing, and the
> infringer prefers to attack than defend (most frequent)
> - the challenger wants to know in advance if it will be necessary to
> pay, and how much, to use a technique, and prefers the case settled
> than live with an unforecasted cost
> - the challenger wants to make money from an existing patent in the
> same field
> - the challenger thinks that for ethical reasons the technique
> described should not be used, like a genetic manipulation technique;
> so the challenger use the tactic of making the patentholder unable
> to get cash by making impossible to license the patent, in order to
> discourage other companies from doing the same kind of research.
> - the challenger thinks that for ethical reasons the technique
> described should be freely usable [use of a genome, which really
> is the same example as above !].
I could be mistaken, but I suppose that, during the public
review period of a European patent, presenting hard materials
to the patent office demonstrating prior art etc. should
suffice to annul the award of the patent involved.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Psuedo-random number generator
Date: 3 Nov 2000 12:47:25 -0500
In article <8ts3j8$8vo$[EMAIL PROTECTED]>,
Alan Rouse <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
> David Schwartz <[EMAIL PROTECTED]> wrote:
>> Who said anything about being balanced or having exactly maximal
>> entropy? I'm talking about having sufficient entropy for cryptographic
>> purposes, nothing more, nothing less
>How much entropy is sufficient? Enough to support the design criteria
>of the encryption. Presumably a cryptosystem designer would select the
>key size, such that the size of the brute force attack would be
>sufficiently large--that is, above some design threshold.
The total amount of entropy in a pseudo-random generaor
is the amount in the key. Running a computer program
cannot generate entropy.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RSA vs. Rabin
Date: Fri, 03 Nov 2000 19:18:36 +0100
Tom St Denis <[EMAIL PROTECTED]> wrote:
> given a != b (mod N) you use a^2 - b^2 = 0 (mod N) to factor N.
Try a=1 and b = N-1. Can you factor N ? Now re-read my message.
In a previous message Tom St Denis <[EMAIL PROTECTED]> wrote:
>>> Rabin is insecure for various other reasons I would imagine.
>>> RSA is more convenient as well. You can easily perform either
>>> operation and you can do signatures, etc..
Then on my comment:
>> One can sign with Rabin (..)
>> Rabin is secure when used with proper message formatting.
Tom St Denis <[EMAIL PROTECTED]> wrote:
> I got that notion from Knuth V2. I can get the exact page where
> he says "The SQRT Box" is insecure for some ops.
That is on page 407 in the third edition of Volume 2, page 389
in the second edition. What Donald Knuth says is perfectly right:
"Anyone with access to a SQRT box can easily dertermine the
factors of its N".
So the trick is not to allow full access to a SQRT box, but only
to a modified SQRT box that, in addition of computing the square
roots, selects the approriate one and checks that it is
appropriatly formatted, else output nothing (but possibly a failure
notice). The principle and motive is given in HAC, Note 8.14.
An example of reasonable formatting is ISO/IEC 9796-2, which
is a signature scheme using RSA or Rabin-Williams.
For examples of formatting with some level of provable security,
see [1] and [2].
Note that formatting is necessary with RSA in many applications,
including encryption to many users, and signature.
Francois Grieu
[1] M. Bellare and P. Rogaway: Random oracles are practical:
A paradigm for designing efficient protocols. Proceedings of
the First Annual Conference on Computer and Communications
Security, ACM, 1993.
Full paper online at:
<http://www-cse.ucsd.edu/users/mihir/papers/ro.html>
[2] M. Bellare and P. Rogaway: The exact security of digital
signatures: How to sign with RSA and Rabin
Advances in Cryptology - Eurocrypt 96 Proceedings, Lecture Notes
in Computer Science Vol. 1070, U. Maurer ed, Springer-Verlag, 1996.
Full paper online at:
<http://www-cse.ucsd.edu/users/mihir/papers/exactsigs.html>
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: ECC choice of field and basis
Date: Fri, 03 Nov 2000 12:29:03 -0600
[EMAIL PROTECTED] wrote:
> It must be a stupid question but what are the reasons for the fields
> GF(p^m) to be disregarded when p>2? Is it a question of security,
> efficiency or lack of knowledge of the EC group structure associated?
It's a good question. One answer is that doing calculations mod p
on most processors is a slow operation, especially compared with XOR.
It's just not efficient with today's hardware. I suspect the same
things found with GF(2^m) apply with Gf(p^m), i.e. you want m prime
to maximize security.
> Mike, on the site of IEEE I have found the page about P1363
> (http://www.manta.ieee.org/groups/1363/P1363/draft.html) but when I try
> to download the draft I am prompted to enter my password. Is the
> standard (freely) available somewhere else?
You can register and they'll send you the password. Or send me e-mail
and I'll send it privately. They just want to know how many people are
actually reading their standard, it's not really secret.
> What are the differences between standards like ANSI X9.62 and IEEE
> P1363 (and ISO 14999-3 and FIPS 186-2 and ...)? Why are there so many?
> Are they in competition or collaborating?
Well, I don't want to get too political, but the main reason there
are lots of standards are because there are lots of people who would
like their software/hardware to be *the* standard. So they all try
to bend the standards to their way of thinking. The US, Europe and
Asia all have their own government standards as well as their own
standards bodies, and each one has their own agenda. Depending on
what product you are making and who is going to use it will determine
which standard you want to follow.
Kind of like RS-232. It's a standard, but you better own a break out
box if you want to hook two things together :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Microsoft's script encoder
Date: Fri, 03 Nov 2000 18:29:10 GMT
In article <8turns$qbe$[EMAIL PROTECTED]>,
"Lefty Louther" <[EMAIL PROTECTED]> wrote:
> When i use microsoft's script encoder (screnc.exe) for
> string :
> response.write ("lakis")
> I get :
> #@~^IAAAAA==@#@&DnkwKx/?RS.kD+~`rVCVb/J*@#@&vwgAAA==^#~@
>
> Does anyone know what kind of cipher algorithm is it ?
It most likely is not an encryption algorithm, perhaps it's a byte code
(like java) stored using ASCII chars...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Fri, 03 Nov 2000 12:48:57 -0600
Mok-Kong Shen wrote:
>
> Dumb question: For GF(2^m) with m sufficiently large, are
> there specific tricks in programming that could speed up
> multiplication/division? Thanks.
Yes, there are great many tricks. One major trick is the choice
of basis. For some field sizes (i.e. depending on m) you can
get a comparable time for multiply and divide where for m+1 you
find the divide routine takes 3 times longer than a multiply.
The use of trinomials makes multiplication faster too.
When m gets very large, say > 1000, you can start using FFT
methods. I haven't had to program that myself, but it's well
described in the literature.
Patience, persistence, truth,
Dr. mike
------------------------------
Date: Fri, 03 Nov 2000 13:52:48 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,talk.politics.misc,alt.freespeech
Subject: Re: Crypto Export Restrictions
Anthony Stephen Szopa wrote:
> Scott Craver wrote:
> >
> > Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
> > >CiPHER wrote:
> > >>
> > >> *waggles fingers* OoooOOOooo! 'Nasty person'! lol
> > >>
> > >
> > >Thank you for your intelligent input.
> > >
> > >Like we really need more of this.
> >
> > ...," he says, posting a follow-up.
> >
> > Have you posted the algorithm yet for your pseudorandom
> > number generator, or is it still just the "help files?"
> > IIRC people could not gleen exactly how the algorithm
> > worked by reading those files, and thus could not subject
> > it to analysis.
> >
> > By the way, since your PRNG uses permutations, it uses
> > "mathematical equations." If you don't think it involves
> > math because it uses compositions of permutations rather
> > than products of large integers, then you need to read some
> > abstract algebra textbooks. And your customers need to
> > _know_ that you need to read some abstract algebra textbooks.
> >
> > You don't need to give out the source code, but something
> > like pseudocode for the generator part would be ideal.
> >
> > -S
> >
> >
>
> "IIRC people could not gleen exactly how the algorithm worked by
> reading those files,..."
>
> How do you know?
>
> What does "gleen" mean? Is that a new toothpaste?
>
> If you don't get it from reading the Help files you need to learn
> how to read. Many many people have read the Help files and ran
> the software and are using the software and they understand it all
> perfectly well.
>
> You, like so many before you, have a wild hair up your ass and do
> not have the slightest ability to simply sit down and work it
> through. It is very very simple. If you are not interested then
> forget about it. You have no excuses. Many others have done
> perfectly well. You have not even tried or have given up.
>
> No one listens to a loser.
>
> If you have some valid criticism of the software post it and support
> your position with facts.
Let me get this straight. You want "valid criticism" of the software you
will not provide or describe. I suppose the "valid" part implies an
objective standard of rigor based on which side of the bed you got out of
and what you had for breakfast?
Here's a fact for you: Your software does not deliver on your promises.
So it is defective.
<high temperature "you" (singular, personal)>
Now you may have a wild hair across a sensitive part of our anatomy and
obviously do not have the ability to simply sit down and work it through.
It is very simple. If you are not interested in this fundamental fact you
should forget about posting in sci.crypt. You have no excuses. Many
others understand cryptography perfectly well. You have not even tried or
have given up.
</high temperature "you" (singular, personal)>
>
>
> So far you are just a whiner who does not do his homework.
And I'm only holding up a mirror.
------------------------------
From: "Lefty Louther" <[EMAIL PROTECTED]>
Subject: Re: Microsoft's script encoder
Date: Fri, 3 Nov 2000 20:58:22 +0200
Can you please be more specific ?
Thank you,
Lefty
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:8tv05b$n87$[EMAIL PROTECTED]...
> In article <8turns$qbe$[EMAIL PROTECTED]>,
> "Lefty Louther" <[EMAIL PROTECTED]> wrote:
> > When i use microsoft's script encoder (screnc.exe) for
> > string :
> > response.write ("lakis")
> > I get :
> > #@~^IAAAAA==@#@&DnkwKx/?RS.kD+~`rVCVb/J*@#@&vwgAAA==^#~@
> >
> > Does anyone know what kind of cipher algorithm is it ?
>
> It most likely is not an encryption algorithm, perhaps it's a byte code
> (like java) stored using ASCII chars...
>
> Tom
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
** 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
******************************
