Cryptography-Digest Digest #47, Volume #11 Thu, 3 Feb 00 20:13:01 EST
Contents:
Re: How to choose public-key e on RSA? (Tom St Denis)
Re: Challenge: Who can discover the encryption used here? ("TJ")
Re: Cipher Challenge $100 to FIRST WINNER ("TJ")
Re: *** ECC - new strong and fast calc method (David Hopwood)
Re: *** ECC Strong and Weak combined (David Hopwood)
"Recipient-hiding" cryptosystems (was Re: Private-key RSA) (David Hopwood)
Re: How to choose public-key e on RSA? ("Miryadi")
Re: ECC & RSA re: patents, copyrights (Paul Crowley)
Re: *** ECC Strong and Weak combined (David Hopwood)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: How to choose public-key e on RSA?
Date: Thu, 03 Feb 2000 22:08:01 GMT
In article <IRsm4.3980$15.28909@news>,
"Miryadi" <[EMAIL PROTECTED]> wrote:
> Peter L. Montgomery wrote in message ...
> >In article <t3nm4.3968$15.28174@news> "Miryadi" <[EMAIL PROTECTED]>
> writes:
> >>
> > Usually e is fixed, for all users. e = 2^16 + 1 = 65537
> >is common. e = 3 has weaknesses.
> >
> Is this e=3 or e=65537 always relatively prime to any (p-1)*(q-1)?
> What If it doesn't?
> So, I guess I've to run my procedure (starting with e=3) anyway.
You are right, it will not always be relatively prime... shortest
example is if
p = 2e + 1 or q = 2e + 1 [for example]...
In this case just make new primes...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "TJ" <[EMAIL PROTECTED]>
Subject: Re: Challenge: Who can discover the encryption used here?
Date: Thu, 03 Feb 2000 23:36:40 GMT
Read the FAQ before I posted, have you? All of it? Boring as hell aint it?
And, lets face it, largely irrelevant. Hell, its the 21st century....:O)
Still, you seem to have missed the point. Software piracy? Who mentioned
that? I deal with trainers and patches and mods for games.
To alter a specific section of a certain game, I need to be able to decrypt
a text file, alter it, and then re-encrypt it.
If you know of another group with as many subscribers of people who may be
up to the challenge, then perhaps you would be so kind as to point me in the
right direction. I only found this group after a search on the www.
Thanks
TJ
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:87arsr$hgb$[EMAIL PROTECTED]...
> In article <pG%l4.1038$[EMAIL PROTECTED]>,
> "TJ" <[EMAIL PROTECTED]> wrote:
> > I have two text files, taken from a game. Originally, the file was not
> > encrypted, and in an updated version, it is.
> >
> > I have a copy of both versions, and my question is this;
> > Who can discover the encryption method used?
> >
> > Thanks
> > TJ
> >
> >
>
> Sure I know what you are talking about... um no.
>
> BTW are you soliciting software piracy? that's a big nono.
>
> Basically... readthefuckingfaqbeforepostingtothenewsgroupplease.
>
> Tom
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: "TJ" <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles,alt.privacy
Subject: Re: Cipher Challenge $100 to FIRST WINNER
Date: Fri, 04 Feb 2000 00:25:16 GMT
My mother is a what?
Anonymous <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Instructions for claiming prize enclosed. One winner, first come first
> served. Expires 1/31/2001.
>
> F B M C J B F S D O O O F M Q U E J P Z P T B B U S B Z O O O U N V Q G
> N N N P I V F F K Q G P U R R K M X V R M Y X S S E S J N T S Y J J N B
> T Z U W M J L K J Y M F D N Y F T X W F D I K J M O Z M B Y S K Y X T N
> K V Z U K L K K P B I A S Q M M W A M W W W Q W M A K F N A B A R Q N R
> J W J F B X J U X U B M X M M F Z B E F T Z D A Q A C S Q V S V G V C S
> R A K C R Q D A F M B G S X C W S C R T R W S W S S R D D M G X N I H C
> T I B C I I I S D U T Q I I V J U J V S G J L L F V J L W J G D W S Z J
> W A W D J A W A G K A P X N X L G B I H W L W L B Q T X M X B W M K Y W
> M M Z X A A I I H L Y O M N Y Z P L X G M H O C B J B X J A P Z Z I D Z
> R E R L O D C A S N
>
------------------------------
Date: Thu, 03 Feb 2000 05:25:23 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: *** ECC - new strong and fast calc method
=====BEGIN PGP SIGNED MESSAGE=====
Greg wrote:
>
> Here is another stab at trying to make things run faster for ECC.
> Assuming that none or only portions may already be covered by
> existing patents, the remainder is immediately submitted to the
> public domain for free use by all.
>
> Patents that MAY have some overlap include 5,987,131.
>
> Given a curve over a field of say 163 bits, I have found
> that average performance in calculating a point multiplication
> can be reduced to 1/3 the time if all points resulting from
> each power of 2 are precomputed and the ones matching the powers
> of two in the private key are then added together.
This is a special case of a well-known technique called "fixed
base windowing", for example see Handbook of Applied Cryptography
section 14.6.3 (which describes it for exponentiation in a
multiplicative group, but it's obvious that it also applies to
multiplication in an additive group). The algorithm you've described
is the case where h = 2.
Chapter 14 of HAC is at
http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf (or .ps);
I strongly recommend reading it. Chapter 3 is also relevant to
this thread.
> This is the part that most likely conflicts with 5,987,131.
Fixed base windowing is not patented. In fact, mathematical
algorithms are not supposed to be patentable (in any country,
AFAIK), although the US Patent Office in particular is very
inconsistent about applying this rule.
[...]
> Additionally, if the key space is limited to 80 bits (in this
> case), the number of point additions on average is cut in half.
> That is, the average time it takes to calculate the resulting
> point is 1/6 of the average using standard calculations using
> a full key space. I argue that security is not weakened for
> the following reasons:
>
> Some have argued that 80 bits is enough to prevent a brute force
> key search attack. This is accepted as obvious.
>
> Some have argued that limiting the private key to 80 bits is enough
> to make the Pollard Lambda (aka Pollard Kangaroo) attack feasible,
> since the attack can be limited by boundaries in the key space.
>
> However, if the bits that are used to define the key are 80 in
> number, it does not matter where they are located. The total
> time to calculate remains roughly the same. Therefore, they
> can span the entire 163 bits in any random fashion.
The sci.crypt thread from November 1999 (title "bits of
diffiehellman private key") that I mentioned before was about
precisely this case, assuming the positions of the 80 bits are
known but arbitrary. In this case the cost of the attack described
there would be 2^41 curve additions (with a fairly large memory
requirement of 2^40 curve points, although it may be possible to
reduce that).
Also note that as pointed out in the notes on page 128 of HAC, an
exponent space with a Hamming weight of t (i.e. there are exactly
t set bits but in unknown positions), can be searched in
k * (k/2 choose t/2) steps (where k in this case is the number
of bits in the largest factor of the group order, if the attack
is combined with the Pohlig-Hellman discrete-log algorithm).
Suppose, for example, that we are using a curve of prime order
over GF(p) with p a 180-bit prime, and exponents with a Hamming
weight of 46 (i.e. just over half as many bits set as normal);
then
180 * (90 choose 23) = 180 * 90! / ((90-23)! * 23!)
= 2^(log2(180) + sum[log2((91-t)/t): t = 1..23])
=~ 2^76.9
(This is an upper bound on the security level, better attacks
are not ruled out.) The field size for equivalent security with
full length exponents is 154 bits, which at first sight looks
slightly less efficient (since the time for a curve multiplication
using fixed-base windowing with h = 2 is proportional to the
square of the field size multiplied by the Hamming weight of the
exponent, and 180^2 * 46 is about 18% less than 154^2 * 77).
However, any performance advantage for the low-Hamming-weight
approach goes away when you consider fixed-base windowing with
h > 2, or other multiplication/exponentiation algorithms (for
example Lam and Hui's string-replacement algorithm mentioned at
the end of the notes for Chapter 14 in HAC).
Bottom line: don't use short exponents or exponents with a lower
than expected Hamming weight for ECC, because it doesn't improve
the security/speed trade-off.
> The randomness of the key bits' locations should effectively
> make the Pollard Lambda attack useless against this key
> space limitation, [...]
There's a difference between making a conjecture that something
is secure, and stating that it "should" be secure. You didn't
have enough evidence for the latter.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOJkQpjkCAxeYt5gVAQFwJwf+PlCt0DTGMS3Ar7E/3KnFVY/+aUmDg/n5
16Y6glQneV7tpF5wtzLGQ+1Xn2zjJXTG1HM2rpavqmeRnE7Ixxd16omuN9ngWgDI
khTGQgfT7LvSC2P35TRMz9hrT+GZ5o8YOpHm3F84PV/DBttud96f/De5lS9hkvYX
TJKSyEKxEcWg2AeaQuWgnFCc+hWCNn4G9mO6Djp2D61h4eZc+6arzJORhllvv0tc
WLYSJ1DbeI1a/K4eXpTUvOA9rsoTvRjOZyEgXK/I4C0OiKi8503Vra0eq3L7ftQS
w2P5DV+iUhEEe4fb0351LNlF65zn1MHFvAwrDEwHaMpoh0uGXDySCw==
=To0J
=====END PGP SIGNATURE=====
------------------------------
Date: Thu, 03 Feb 2000 06:48:48 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: *** ECC Strong and Weak combined
=====BEGIN PGP SIGNED MESSAGE=====
Greg wrote:
>
> > > I thought that n was related to the field size, not the number of
> > > bits in the private exponent that can vary.
> >
> > No. To be a little more precise, n would be the minimum of the number
> > of bits that can vary in the private exponent, and the bit-length of
> > the largest prime factor of the curve order.
>
> I have never heard this before. Where can I find a paper on the
> Pollard Lambda attack that explains this in some detail? After
> reading this post of yours, I have been searching the web and found
> nothing yet.
I can't find any detailed descriptions (or any descriptions at all,
for that matter) of Pollard lambda on the web either. Pollard's
original paper, which describes both Pollard rho and lambda, is:
J. M. Pollard,
"Monte Carlo methods for index computation (mod p),"
Mathematics of Computation, 32 (1978), 918-924.
but you'll need a good library to find that.
> > To get the best possible security/speed trade-off, IMHO you
> > should use a random curve with a known prime or "nearly prime"
> > order ("nearly prime" means a large prime multiplied by a small
> > integer cofactor, say 2 or 4), and a full-length exponent.
>
> The problem here (for me) is that it is random and you are never
> sure how strong the curve might be- or more precisely, how weak
> a particular instance of encryption might yield.
This is true to some extent for any public key cryptosystem. The
security of a public key system is based on the parameter and key
generation processes having "sufficiently low" probability of
generating weak results. I'm not going to try to describe all the
checks needed to avoid known attacks against particular curve
types here (by saying "use a random curve", I did not mean to
imply that these checks should not be done); see IEEE P1363 for
some recommendations.
> > If you have performance problems, it's better to decrease the size of
> > the field but keep using full-length exponents, than it is to decrease
> > the exponent length [*]. This is because a curve multiplication takes
> > time proportional to the cube of the field size (for full length
> > exponents), while shortening the exponent only gets you a linear
> > speed-up.
>
> I found this interesting and it turns out that when I looked at
> my data you were right. I found that my data follows your claim
> quite precisely.
It is actually possible to do better than O(m^2), where m is the field
size, for curve addition (and hence better than O(m^3) for curve
multiplication), but it's rarely worthwhile to use the more complicated
algorithms for the range of field sizes typically used for ECC.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOJkkgjkCAxeYt5gVAQFVCwf9HtJUQMEFvoJNnzx5zO4mRFEPiwzXR7U9
y3LRhfl8vHLpa6qVwIwredzeGMvMJYInFSUAhdJCYis+iHZ95gJAufK7sAlSy79Z
Ym3J7tO1ahABspnA1qod/KXB5CvSrMpej5y+LXnBuuvMSkmIecFt4OKmxEdj5Cvs
noxu7xhyn10nFjt8mv0xy7lVTrwquFc9ipBbNkGZeAKiubmd6mUSR7sUlI/U1aTM
a09K/7/QkaG+YXk8y9vGbrBzzqtExAAcjZ7dSw6D3IZ0pfHjEvpfTv/3tZqu6sc6
VRlEs+D7oSd1+arDNkgcdlSms1q92ytyswnHcq4ezD2yfKAIhK0Ugw==
=ZNUr
=====END PGP SIGNATURE=====
------------------------------
Date: Fri, 04 Feb 2000 00:39:48 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: "Recipient-hiding" cryptosystems (was Re: Private-key RSA)
=====BEGIN PGP SIGNED MESSAGE=====
David A Molnar wrote:
>
> [EMAIL PROTECTED] wrote:
> > Hi,
>
> > Surely if you encrypt using RSA, but both the public-key and exponent
> > are kept secret (i.e. not widely published), the cryptanalyst has a
> > nigh on impossible job?
>
> That's an interesting question. Given a message encrypted with RSA (or
> some other cryptosystem), can you identify the public key used to
> encrypt?
>
> Note that this has implications beyond the security scenario you
> are suggesting. In particular, consider an anonymous remailer with reply
> blocks pointing to a public newsgroup. The remailer encrypts with the
> final recipient's public key and posts the message. If an adversary can
> determine what the public key of a given message is, he can monitor
> when that key gets mail.
[...]
> First we need a definition of what it means to be unable to "determine the
> correct public key." A while back I was playing with something like this :
>
> (informally stated, but can be made more formal if you want)
>
> Let's say our adversary is given a ciphertext C, and the corresponding
> plaintext P. He has two public keys K_1 and K_2. He knows that C is
> the encryption of P under either K_1 or K_2 (he's managed to narrow
> it down to these two somehow).
>
> So he knows that C = K_1(P) OR C = K_2(P) .
>
> Now he must tell which one.
The usual type of model would be to allow the cryptanalyst many
plain/ciphertext pairs encrypted to the same key, and to consider an
attack a success if the two public keys can be distinguished with
probability greater than 1/2 + 2^-t for some security parameter t.
> We might say that a cryptosystem is "recipient-hiding" if the probability
> of the adversary for successfully distinguishing K_1(P) from K_2(P) in
> polynomial time is negligible. On the other hand, we might call a
> cryptosystem "recipient-leaking" or "recipient-advertising" if the
> adversary can _always_ distinguish K_1(P) from K_2(P) in polynomial time.
RSA with OAEP is not recipient-hiding if a sufficient number of plain/
ciphertext pairs are available, because for a candidate public key with
modulus N, we expect RSA ciphertexts to be approximately uniformly
distributed on [1, N-1]. If they are not (as determined fairly simply by
statistical tests), then we have the wrong modulus, and therefore the
wrong key.
Elgamal and other DH-based cryptosystems are not recipient-hiding if
each user has different parameters, for the same reason as RSA. I *think*
Elgamal is not recipient-hiding even with common parameters, because of
the problem it has with leaking whether the plaintext is a quadratic
residue. DHAES with common parameters might be OK.
[DHAES, and the information leakage with Elgamal, are described in:
Michel Abdalla, Mihir Bellare, Phillip Rogaway,
DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem,
Contribution to IEEE P1363a.
http://grouper.ieee.org/groups/1363/contributions/dhaes.pdf (temporary), or
Theory of Cryptography Library.
http://philby.ucsd.edu/cryptolib/1999/99-07.html
]
> A recipient-hiding scheme seems to be something useful for anonymous
> protocols in which encrypted messages are seen by an adversary.
I agree.
> The advantage of a recipient-leaking or recipient-advertising scheme
> might be in offering an easy way to store and search encrypted messages,
> depending on their destination.
You can achieve this simply by including the destination with the
ciphertext (signed if necessary), so I don't think that this is
particularly useful as an attribute of a PK encryption algorithm.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOJezFzkCAxeYt5gVAQFufwf/VIqA1gr8ZQO0ARN47RmBfLBAAg4++pHN
T2TNSVP4vyQs32buVTU2D2ZR3mshSfdWQtJY4cA5NlRxkMF9B4XrMSaTtiJVgk4W
WH8gzuclWoLN08psOAwREWdKMxJOwK3w6ta2MKFkaJB10ISSYJ8qCCkaGoLhoTQk
aMKN+5UVWBsXaNV6eCIr95IOP8tGg1Nexp1ljX9O9ro2t4RJ3HiTVEOfonH6Exdd
OFy20ZaDoiQ1ILhvr5ujZc4iwbmWDTCrrVsmryPXaVs4U5/KHzex8iM0pG+KlUx9
XeCBqDYsWIO12vTWVEjYqfPfP8TuuHxPzQ/MJV1YJDBemFkluQEh7w==
=r96C
=====END PGP SIGNATURE=====
------------------------------
From: "Miryadi" <[EMAIL PROTECTED]>
Subject: Re: How to choose public-key e on RSA?
Date: Fri, 4 Feb 2000 07:45:13 +0700
Tom St Denis wrote in message <87cu7t$1e$[EMAIL PROTECTED]>...
>
>You are right, it will not always be relatively prime... shortest
>example is if
>
>p = 2e + 1 or q = 2e + 1 [for example]...
>In this case just make new primes...
>
So, you mean that I better search for new p and q, with that fixed e,
rather than try to search for new e that is relatively prime to (p-1)*(q-1).
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: ECC & RSA re: patents, copyrights
Date: 3 Feb 2000 18:50:23 -0000
[EMAIL PROTECTED] (Bill Unruh) writes:
> Whether or not software in general should be patentable is a
> different issue. RSA is not a patent on software. It applies equally
> well if you implement it in a set of gate arrays, or however you
> wish. Implimenting it in software is one one possible way.
In the usual way of discussing these things, any patent that can be
infringed by a piece of software is a patent on software.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
Date: Fri, 04 Feb 2000 01:05:40 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: *** ECC Strong and Weak combined
=====BEGIN PGP SIGNED MESSAGE=====
David Hopwood wrote:
[...]
> > [...] Where can I find a paper on the Pollard Lambda attack that
> > explains this in some detail? After reading this post of yours,
> > I have been searching the web and found nothing yet.
>
> I can't find any detailed descriptions (or any descriptions at all,
> for that matter) of Pollard lambda on the web either. [...]
Found something:
http://www.cacr.math.uwaterloo.ca/~eteske/teske/course/course_notes.html
There are also some interesting papers at
http://www.cacr.math.uwaterloo.ca/~eteske/
Note that Pollard lambda is also called the "kangaroo" method.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOJoluzkCAxeYt5gVAQHusggArM2P23WVZcwcqe+TrWlUFIyS58mWqj0E
PdpenivHoJHvEnlgdvpHkq290vO9ZuoWuDmk8GIQ4/G70OLQGuc8OiWFY5wX/bP1
P5SqQZrMxEDUMRfO3Tki4/1OLqTD3RiogXCEqwon/5oBdFNiQznys4uuLrOilu9H
oS7jfrFc669VkIO+5qpHV8W2grY2MmosbPrJu2JoRn4LbJgH0lkuNI6qNhyHtAa4
AtdliBD0lE92YyHiYb/3MyVLLfrUjZreC3gvM548pv6krb4X6v+wWv0cZiwEtY7K
8ck45hkKCgMxfuS+g275oU+OQEwRRkt3O4wT9XfECNgXkc2t1sn51g==
=1UFO
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
