Cryptography-Digest Digest #55, Volume #11 Sat, 5 Feb 00 12:13:01 EST
Contents:
Re: NIST, AES at RSA conference (John Savard)
Re: Factorization ("Peter L. Montgomery")
Re: finding gcd in the large multiplicative group... (David Hopwood)
Re: NIST, AES at RSA conference (wtshaw)
Re: NIST, AES at RSA conference (wtshaw)
Re: Factorization (NFN NMI L.)
Key Generation program for Windows? ("cedric frost")
Re: NIST, AES at RSA conference ("Joseph Ashwood")
Re: How to Annoy the NSA ("Douglas A. Gwyn")
Re: Factorization (Scott Contini)
Re: How to password protect files on distribution CD (The Archmage)
Re: Key Generation program for Windows? (Steve K)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST, AES at RSA conference
Date: Sat, 05 Feb 2000 05:48:25 GMT
On 4 Feb 2000 16:27:07 -0800, [EMAIL PROTECTED]
(David Wagner) wrote, in part:
>Yes, sure, but Terry Ritter claimed that multiple ciphering is
>strictly *stronger* (i.e., >, not just >=). Such a claim is, as far
>as I can see so far, unsupported.
I don't think he meant to say that it was proven strictly stronger,
but simply that from a practical point of view it is very likely to be
so (particularly when one uses three layers, to take into account the
meet-in-the-middle attack) with reasonable choices of ciphers.
I know alternating between a practical viewpoint, and saying that
AES-class ciphers are necessarily inadequate because they can't be
_proven_ strong, is both kind of confusing and open to criticism...
but there is really only one gap in Terry Ritter's argument. The only
missing link is some grounds for considering the AES candidates as
likely to be inadequate, or in need of additional reinforcement, from
a _practical_ point of view as well. Everything _else_ falls into
place neatly enough.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Subject: Re: Factorization
Date: Sat, 5 Feb 2000 06:09:50 GMT
In article <[EMAIL PROTECTED]>
[EMAIL PROTECTED] (NFN NMI L.) writes:
>Hello. Would someone please run 5154228018862208512867 through a math package
>and tell me:
>- its factors (2 primes roughly the same size - RSA, you guessed it)
>- the name of the math package (any will do, Mathematica, whatever)
>- how long the factorization took
>- what system, roughly, it was run on (P2 400Mhz, say)
>
>Thanks. My poor TI-92+ is choking on this number and I don't have Mathematica
>on my computer. :-(
>
>S. "Money sucks, except when you have it" L.
On one processor of an SGI Origin 2000, P-1 and Pollard Rho
were unsuccessful, and quit after a second.
Then ECM took 0.06 second to factor the number in step 1.
A second ECM attempt took 0.31 second to factor the numeer in step 2.
Montgomery factorization program. Compiled Tue Jun 3 21:25:54 MET DST 1997.
Allows inputs up to about 6300 decimal digits.
5154228018862208512867
Composite cofactor has 22 digits:
5154228018862208512867
RAND_PRINT - Current random number seed is 198181203 527043255 233382925
Using 4 curves of order divisible by 12 and limits 2000 600000
CHEK - Nontrivial GCD ECM
53401798669
The first number below is the product of the second and the third, as found
by ECM after 51505 multiplies and GCDs
in 0.06 CP seconds at Sat Feb 5 07:01:27 2000
5154228018862208512867
53401798669
96517872943
Probable prime cofactor has 11 digits -- terminating.
--
E = m c^2. Einstein = Man of the Century. Why the squaring?
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
Date: Sat, 05 Feb 2000 04:43:56 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: finding gcd in the large multiplicative group...
=====BEGIN PGP SIGNED MESSAGE=====
Taekyoung7 wrote:
>
> Hi, all...may somebody answer my stupid question. Thanks...^^;
>
> Finding g.c.d. in the large multiplicative group is trivial, am I
> right?
gcd is an operation on integers, not group elements, remember.
If the group is Z*_p, then finding the gcd of several elements
*considered as integers* is trivial, yes.
> For example, if we have g^x*g^y1, g^x*g^y2, g^x*g^y3,...,g^x*g^yn
> (mod p) where g is a generator of a multiplicative group Zp^* and
> we try to find the gcd through the Euclidean algorithm, then...
> does the g.c.d. of them converge to g^x with n in its reasonable
> size. Am I right?
No. (g^x * g^yi) mod p will sometimes be less than g^x, and sometimes
greater than g^x, so its gcd will not converge to g^x (unless x
happens to be 0, to be pedantic).
Technically the gcd converges to 1 (when one of the yi = p-1-x), but
that won't occur for any reasonable size of n if the yi are chosen
uniformly at random.
> (please note that x is chosen once at random and each y^i are also
> chosen at random in [2,p-1].)
>
> Thanks in advance...
- --
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
iQEVAwUBOJuqfzkCAxeYt5gVAQEwUQf/UrO4D76KoFgk/+8k9ujuPhVbyyMMdvui
rJGYgjS5L075hb1OL1/FIHreudp/apdlvJXfpzyuAOtLK+/buOLxvhKYWX0Pu7K+
Vt6UbZu4p9CNTPWdHxYi0UTQpQyh/1HC0HbKCiAHlFakHwuY15G6ktvXuVRzvMEb
PoxryMzBlDutc/zkTYTHiEo7Aj5yV2FCh+xgJlLX/kszLyejV562q1FePIKRoijN
dcYfNscNouvwGX4qm4P1yve/3dQFcKKTP76GdNUUDZWvZr6XeGx8enN6xpgJMtPl
P6WxI897xweIZN2He2e3ZyQb/ZjGLp1M3w8A4ckfDIDguYUFZnR7Hw==
=WoxM
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: NIST, AES at RSA conference
Date: Sat, 05 Feb 2000 00:29:30 -0600
In article <87fqor$ba5$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> Yes, sure, but Terry Ritter claimed that multiple ciphering is
> strictly *stronger* (i.e., >, not just >=). Such a claim is, as far
> as I can see so far, unsupported.
For multiciphering, as in chaining, not to add strength, the algorithms
must have similarities such that sometimes the results are actually weaker
than one alone.
Where different and mostly exclusive mathematics are involved in different
algorithms, you are going to have difficulty finding where strength is not
increased. The opportunity to increase key space by using plural
algorithms is additive for the keyspaces involved.
--
A big-endian and a little-endian have been spotted sitting at a
campfire nibling on bytes and pointing at each other as they
argued about who got hit with the most errors.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: NIST, AES at RSA conference
Date: Sat, 05 Feb 2000 00:31:11 -0600
In article <eZXhEK3b$GA.315@cpmsnbbsa02>, "Joseph Ashwood"
<[EMAIL PROTECTED]> wrote:
> > Yes, sure, but Terry Ritter claimed that multiple
> ciphering is
> > strictly *stronger* (i.e., >, not just >=). Such a claim
> is, as far
> > as I can see so far, unsupported.
>
> Actually the statement that it is strictly stronger can be
> easily contradicted, using XOR (eXclusive-OR), where
> regardless of the keys chosen multiple encipherment is
> strictly equivalent to a single encipherment with the XOR of
> the keys.
> Joe
You must be only familiar with one type of algorithm to consider them all alike.
--
A big-endian and a little-endian have been spotted sitting at a
campfire nibling on bytes and pointing at each other as they
argued about who got hit with the most errors.
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: Factorization
Date: 05 Feb 2000 07:23:11 GMT
Wow! So many replies so fast! :-D
Thanks for everyone's help!
S. "Now I can make HP calculators look bad, heh heh" L.
------------------------------
From: "cedric frost" <[EMAIL PROTECTED]>
Subject: Key Generation program for Windows?
Date: Sat, 5 Feb 2000 03:08:32 -0500
Anyone know of a program for Windows 9x that generates pseudo-random
keys/passwords? I use Counterpane's Password Safe for storing keys, but its
password generator only produces alphanumeric results, and there are no
claims about its randomness/security. I would like something that will help
me generate keys using any printable character, or perhaps a customizable
choice of characters.
Thanks,
Cedric
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Sat, 5 Feb 2000 01:13:11 -0000
> You must be only familiar with one type of algorithm to
consider them all alike.
I was in no way considering them all alike. The given
statement was that (1) for all ciphers the use of
multienciphering strictly increases the level of security.
My example was a very well defined counterargument, using an
easily understood cipher. My point was that it is certainly
not true that even with reasonable bounds on the key choice
(any choices would work for my example) the security is
strictly increased, and in my particular example it failed
to increase the security. My statement was that there are
cases where multiple encipherment fails to increase the
security, a contradiction to (1).
My example did not require that all it be true that the
level of security is never increased regardless of the
cipher choices, only that there are choices of cipher that
do not increase the security. While I did not make
statements of the type, it is likely that for carefully
chosen ciphers with carefully chosen keys the security is
even reduced, and there are certainly choices where the
security is increased. There are probably choices where
f(x,g(y, m)) = g(y,f(x,m)) = g(x,f(y,m) = etc.
If you somehow came to the conclusion that I was inferring
that for all cipher the security can not be increased than I
would say that your conclusion is wrong as we have a rather
prominent example that is believed to be in that realm, the
example being triple-DES.
Joe
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How to Annoy the NSA
Date: Sat, 05 Feb 2000 09:43:37 GMT
David A Molnar wrote:
> Actually, Jerome Solinas seems to attend some of these conferences,
Some NSA employees have also contributed (on occasion) to this
newsgroup, but if they monitor it, it is mainly for their own
personal amusement and perhaps a desire to be helpful, not "to
find how good various people are".
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Factorization
Date: 5 Feb 2000 11:24:11 GMT
In article <[EMAIL PROTECTED]>,
NFN NMI L. <[EMAIL PROTECTED]> wrote:
>Hello. Would someone please run 5154228018862208512867 through a math package
>and tell me:
>- its factors (2 primes roughly the same size - RSA, you guessed it)
>- the name of the math package (any will do, Mathematica, whatever)
>- how long the factorization took
>- what system, roughly, it was run on (P2 400Mhz, say)
>
>Thanks. My poor TI-92+ is choking on this number and I don't have Mathematica
>on my computer. :-(
>
>S. "Money sucks, except when you have it" L.
Here is the computation done on a 333Mhz Sun Workstation:
Magma V2.6-2 Sat Feb 5 2000 22:13:10 on galois [Seed = 1]
Linked at: Sat Feb 05 2000 21:52:58
Type ? for help. Type <Ctrl>-D to quit.
> time Factorization (5154228018862208512867);
[ <53401798669, 1>, <96517872943, 1> ]
Time: 0.479
>
(It took about a half a second). This is done with the Magma computer
algebra system. Magma is a interpreter language designed for computation
in algebra, number theory, and geometry. Cryptographers will find
it a very useful tool to aid them in their research, teaching, and
learning. I have a postscript file that gives several examples of Magma
applied to cryptography. E-mail me if you'd like a copy.
For more information on Magma see:
http://www.maths.usyd.edu.au:8000/u/magma/
Scott
------------------------------
Date: 5 Feb 2000 16:38:47 -0000
From: The Archmage <[EMAIL PROTECTED]>
Subject: Re: How to password protect files on distribution CD
Crossposted-To: alt.security.pgp,comp.security.unix
=====BEGIN PGP SIGNED MESSAGE=====
Eric - for the most part I agree with you I made one comment below
On Thu, 03 Feb 2000 14:13:02 -0700, Eric Lee Green <[EMAIL PROTECTED]> wrote:
> > - for more than 20 years, reasonable computer systems, including all that
> > I've been involved in designing, have had application-readable serial
> > numbers.
>
> That's nice. That doesn't have anything to do with my situation, which is that
> MAC addresses are mutable objects on personal computers and thus not suited
> for use
I wanted the above reprinted
> > ]I don't know what my management would do, but I suspect it would NOT be
> > ]polite, at a minimum with irate demands that you fix the problem [and possible
> > lawsuit filed under state consumer protection laws]
> >
> > That is an distinctly silly pile of nonsense. I hope it was a
> > mistake instead of typical.
>
> Really? What's the deal? I pay $30,000, I expect a service, and my state's
> laws say that you are required to grant a service ("implied warranty of
> merchantability"), no matter what any contract says. Contract terms which
> violate the law are unenforcable, in case you missed that lecture when you
> took Business Law 101 in college.
>
> The first thing I would do, of course, would be to notify the vendor that
> their program had quit working and ask them to fix the problem. But if this
> program is running my business I'm dead in the water until it's fixed. For a
> manufacturing firm, that's not small potatoes... I could be losing hundreds of
> thousands of dollars per day here. That's plenty reason to get upset.
This is typical and I agree with you. In general software costing $30,000 and
above is often crucial to a businesses operation. The customer of this
software will expect it to work, expect speedy turnaround time on support and
wouldn't expect it to break if upgrading the network card of the accounting
guy in charge of payroll. Hell if they didn't know that MAC addresses were
part of the licensing scheme they may not even report it when they call in the
problem to support, when they find out that a non-obvious upgrade or
maintainance procedure caused N hours of downtime they will raise hell.
> > What "normal" license manage does not not involve a hardware serial number
> > or signature of some kind?
>
> Windows 98? Just about all PC software that I've ever encountered that's
> licensed on a per-user vs. per-seat basis?
I agree, most licenses are sold per seat/per user. It is a simple heuristic
that is easy to market. Complex schemes are hard to sell.
>
> > The fatal difficulty with any scheme not based on hardware is that it is
> > too easy to copy all files of an application, including files containing
> > generated hashes. An honest customer that accidentally copies a $30,000
> > package onto a new system for a new or spun-off subsidiary or distant
> > office, and finds that no new key is required will probably forget to call
> > the vendor for another key.
>
> So you say. But there's a couple of things going on here:
>
> 1) Usually, if you have an expensive package of that sort, you also have a
> service contract. Getting calls from another site is going to be a sure-fired
> tip-off that something's gone wrong! In real life that's the primary way we
> detect unauthorized copies of our software -- such calls are then forwarded to
> Sales in order to outfit the guy with the proper product legal and all.
>
> Undoubtedly there are illegal copies of our software floating around.
> But not at our big customers, all of whom have site licenses with us
> for a certain amount of copies of our software. We operate on the honor
> system there at the moment, rather than trying to create a network
> license manager that would work on all dozen or so platforms that we
> support. See #3 for another issue.
Sure, but there will be an (acceptable?) amount of leakage of actual license
counts. Still cheaper than the support costs of most licensing schemes
including dongles.
>
> 2) If a firm can afford a $30,000 package, it's unlikely that they can afford
> to be sued for running an illegal copy of said package. In my experience,
> companies are quite paranoid about the expensive stuff.
Here I disagree. It really depends on the market. If the software caters to
a vertical market you may find out that there are only a 100 companies
world-wide who are your market. Sure you charge $100000 for licensing, but
one lost license hurts. There is software running on oil rigs that provides a
good example of this. The software to run one rig is in the $50,000 range.
Adding one more rig is a big deal, cutting out the software skims a little
money off the cost. Just copy the stuff from Rig X.
Note this idea fails in certain areas as well. I know a number of Israeli
startups who will happily pirate software, $30,000 or not. I have see other
companies in NYC pirate software from word to their ERP licenses. Sure if the
top is aware of it, they may get nervous and may come clean in the future.
But many times pirating is occurring on the departmental level when they can
fit a purchase in their budget. Sure most of this is incremental, buy 10
licenses for the company when their are 38 current users, or why buy licenses
for our new office in Chicago, their on the same WAN right.
> 3) We're not concerned about teenage haxxorr types pirating a $30K package.
> They're not going to buy a copy of it anyhow.
This is an issue that depends on the markets you sell to. In Russia, China,
Japan and some parts of Europe cracking is a business and a serious one. The
crackers will sell your $30K cracked package through business consultants
(VARS) who help companies install it.
- - --
The Archmage : We are watching...
[EMAIL PROTECTED] : ... and being watched.
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQCVAwUBOJu345EmLpvFTp2hAQGw4wP/X71v7ZtkdNPc7Fl1IdBLXmG/O+wRFHdi
1FuWfmF4LJdWyuZaQ1XUUQx0p50hQOYSn7CtbSBlSFz4B+cH703ucvM+hFYuGxjv
EYmVJBZSVi1e9lm2Mrdi49+j/ldbErARv4MrlGrAFbYW2Xu1KdNZemmJCoDgzfF6
W/hvq+KJBQo=
=TgYU
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Subject: Re: Key Generation program for Windows?
Date: Sat, 05 Feb 2000 17:07:50 GMT
On Sat, 5 Feb 2000 03:08:32 -0500, "cedric frost"
<[EMAIL PROTECTED]> wrote:
>Anyone know of a program for Windows 9x that generates pseudo-random
>keys/passwords? I use Counterpane's Password Safe for storing keys, but its
>password generator only produces alphanumeric results, and there are no
>claims about its randomness/security. I would like something that will help
>me generate keys using any printable character, or perhaps a customizable
>choice of characters.
This is not exactly what you wanted, maybe, but I think it's a pretty
OK work around: You can use any decent crypto program for text, as a
strong pseudo-random number generator with (typically) 64 bits per
charachter of entropy in the output. This works out to a *large*
number of 8 charachter password.
64 bits x 8 bits = 512 bits, so
2^513 minus one = 2.68 x 10^154 unique 8-letter passwords.
(I won't be surprised if someone corrects these figures.)
Just select a chunk of text "at random" from any text document,
encrypt it to a key that has not been distributed, and pull your
pseudo-random password out of the resulting mess. PGP will do
nicely;grab a string out of the middle of the encrypted block. You
can filter out weak passwords by picking a string with more than one
kind of charachter in it.
:o)
Steve
---Continuing freedom of speech brought to you by---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
PGP key 0x5D016218
All others have been revoked.
------------------------------
** 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
******************************
