Cryptography-Digest Digest #265, Volume #14 Sun, 29 Apr 01 18:13:01 EDT
Contents:
Re: Note on combining PRNGs with the method of Wichmann and Hill (David Hopwood)
Re: Reusing A One Time Pad (David Hopwood)
Hiding plaintext length (was Re: Reusing A One Time Pad) (David Hopwood)
Re: Secure Digital Music Initiative cracked? ("Tom St Denis")
Re: Secure Digital Music Initiative cracked? (Xcott Craver)
Re: Censorship Threat at Information Hiding Workshop (Xcott Craver)
Re: Censorship Threat at Information Hiding Workshop ("Tom St Denis")
EC encrypt/decrypt (CrapMail Bait)
Re: GF(2^m) ("Peter L. Montgomery")
Re: GF(2^m) ("Tom St Denis")
Re: Announcing A New Rijndael Encryption Algorithm Implementation (CrapMail Bait)
Re: RSA BRUTE FORCE ("Jack Lindso")
Re: DSA in GF(2^W)? (CrapMail Bait)
Re: DSA in GF(2^W)? (CrapMail Bait)
Re: DSA in GF(2^W)? (jlcooke)
Re: DSA in GF(2^W)? ("Tom St Denis")
----------------------------------------------------------------------------
Date: Sun, 29 Apr 2001 21:29:45 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
> Addendum: The scheme of Wichmann and Hill is intended
> to get a more uniform stream from a number of not well
> uniform streams. The assumption I made above that
> the PRNGs are uniform is for discussion of the
> theoretical point you raised which I quote below:
>
> The modification destroys an important property of
> the basic combination method: as long as the streams
> are independent, if any of the streams are uniform
> then the sum is uniform.
>
> So in that situation we assume that there are uniform
> streams to start with.
We assume that there is *at least one* uniform independent stream.
Bryan Olson's point is absolutely correct: it is obvious that the
modified Wichmann-Hill scheme, with weights that are not all
non-zero integers, does not have the property stated above.
(Counter-example: if the only uniform stream has a weight that is not
a non-zero integer, then after weighting it is not uniform. If the
other streams are also non-uniform, then in general the sum is not
uniform either.)
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOuxJFDkCAxeYt5gVAQH9DAgAnBV69NAmzsnCWLoE4SAZF4cfvr4vKxNO
GFOGlOf64KZQsYdImftcfVCaJP5O3O5rDnvG/uxgmsmK/5CpNu6cgKx8xP3GYGKy
Maqy+HWfXDcShnitVnyyRhRYufEpWjx2Mnkxkak6JbO7eXIc0PrBfGEFDpUZmeW3
O/zXf/+JBAX9sHlIqU1ULGTgyle2RwrOgoU84WEUqA/PXdWM9htnwjgoec3tv6Kw
bEeuUIedPMDgMfMizXSuJi1QUdfHjJBchfJvDRtv+puF0txGwqYu68xeaeZK22+/
kBDlSO2A51jPd958u6SL7JtnujbFzWRyobNDPOqJNsUGt1bNZXGQ9w==
=Dh6z
=====END PGP SIGNATURE=====
------------------------------
Date: Sun, 29 Apr 2001 21:30:02 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
=====BEGIN PGP SIGNED MESSAGE=====
Scott Fluhrer wrote:
> Mark G Wolf <[EMAIL PROTECTED]> wrote in message
> news:9bdfjg$1v8m$[EMAIL PROTECTED]...
> > ... I mean even if you used the same pad many
> > times over a long period you'd have to assume that someone was actually
> > collecting all your messages, which is not very likely.
>
> Well, yes, if your threat model is "your kid sister", then yes, there's
> nothing insecure about reusing your "OTP".
Speak for your own kid sister :-)
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOuxi8jkCAxeYt5gVAQEFsAf+NuyYyVbe0VzEdrtWIApiVKLspm3sjEoW
J0broLP2LufYYbCR/4N+8WwtpxUgmVbKfv59Cm8wp+t16Z/LI5RvK/h+7pmyg/k1
CKdHeL8Ie2DUNE10j8XKJTTY0Q1Owoecn+vjfh7f0/4kTa4LdxFas4uYUP/HuQpJ
dwkPoqLamOTvYan9XAIUfU+LBp2vF4YaxricZNJH4OHKMQcZas33UtBzS7ldeTbF
iGiybSz+CRKodKQ6gGJsIdi2Uml8u8itBIWZZa6+y/hNAAr3wbMaxeMN0vhFYrwV
hB95vo2jQAqimwtY6h1Pi01WIg5xin2bZQzWOPi93XNuMrMe49DHxg==
=3jfB
=====END PGP SIGNATURE=====
------------------------------
Date: Sun, 29 Apr 2001 21:30:54 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Hiding plaintext length (was Re: Reusing A One Time Pad)
=====BEGIN PGP SIGNED MESSAGE=====
Tom St Denis wrote:
> "SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > [EMAIL PROTECTED] (Tom St Denis) wrote in
> > <fLiD6.43031$[EMAIL PROTECTED]>:
> >
> > >"Modestly large OTP" is a meaningless description. An OTP must by
> > >definition be the same size as the message. And if it's a true OTP
> > >you need not encrypt it any "further" to get a more secure system,
> > >it's already provably secure.
> >
> > Actually an OTP does does not have to be the same size as the
> > message sent. Suppose one defines the set of all messages that
> > one wants to encrypt to be 1000 bytes max. By 1000 bytes I mean
> > that is the length after compression and the bijective padding
> > transformtion to get the data to exactly 1000 bytes. At this point
> > you use 1000 fresh bytes of your OTP to encode the message. This
> > would be far more secure than using a OTP on the message and
> > leaving the length information there for the taking.
>
> Um no actually you're wrong.
For once David Scott was making a perfectly sensible point (which also
applies to other algorithms than OTP).
> Even given the length of the message you
> cannot break an OTP. Knowing the length does not give you any useful
> information about the actual message other than's it's length.
And what is that, if not "information about the message"? In some cases
the length of the plaintext can be very useful to an attacker. For example,
in a mix-net protocol, length information can be used to completely break
the anonymity goals of the protocol, if it is not hidden by making messages
a uniform length. In HTTP or Telnet over SSL/TLS, the length of packets may
reveal information about which pages on a site a user is visiting, or which
commands are being sent. The usefulness of hiding length information is
certainly not restricted to artificial examples like "yes" vs "no".
> This could be used if you are replying with "yes" or "no" but real
> english is typically larger...
Real protocol packets are not necessarily larger. Even if they are, in
some cases the slightest amount of information (for example being able
to distinguish different categories of message, without knowing their
content) may be all that is needed to perform an attack on the protocol
that is being encrypted.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOuxpRjkCAxeYt5gVAQE2QwgAj7j/UxWxKPKRybC7M11rUe00WqXSR+tA
fKImJEuuGIM9A21DwXp7IDghAjnwG+3gm5vVPpe5whOfBQbyJbvqPgoFwuMCQy5l
ksuLFAmg3QnMksGl4fcnaVuPnd1TePe6FaSMnwywSZ9KI56f+hvjeLo2or0lD3/Z
A6JyJQAC6+kjuBICYIxZk5CHdcbd7dbVuITkVmU0razryuPgljAjx+JFZ4QTj1NU
ci5o9LJzEzcZ+HrSqTKd/hE1ZISAjCw+yHYyBdhjBFENFk3dmZs9tlZTrao7PTNN
1GcjwGr65oZLIEUULHE/laFTBI9h7rND5p/kfjJU67Cca3NYpDbX2A==
=/YvU
=====END PGP SIGNATURE=====
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Secure Digital Music Initiative cracked?
Date: Sun, 29 Apr 2001 20:33:29 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"M.S. Bob" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > "M.S. Bob" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > David A Molnar wrote:
> > > >
> > > > Roger Schlafly <[EMAIL PROTECTED]> wrote:
> > > > * If it is too dangerous to take information from the
> > > > manufacturers and illegal to take information from
> > > > reverse
> > > > engineering devices, then *how* is research on these
> > > > technologies
> > > > to be conducted? (I am taking it as a given that such
> > > > research
> > > > should be undertaken).
> > > > Do we know how broad the DMCA's exemption for
> > > > security research is?
> > >
> > > Well if the DMCA was law earlier in US history, then the DMCA
> > > could of been used against:
> > >
> > > RC4/ARC4
> > > WEP
> > > PTPP
> > > NT LAN Manager (NTLM)
> > > A5 (the US effort, at Berkeley)
> > > Netscape random number genenator
> >
> > To add to this list
> >
> > The three RSA inc. DES challenges
> > The RSA RC5 challenges
> > The RSA RSA Challenges
> > The Certicom ECC challenges
> > The Samba hash crack (the one that uses a single round of DES
> > etc..) The Unix hash cracks (basically any password cracker).
> >
> > Not to mention the wealth of public cryptanalysis that fills
> > euro/asia crypt journals.
>
> The algorithms I mentioned were reverse engineered without the
> author/designer/owner/whatever's express permission. The RSA
> Security Inc and Certicom's challenges were with their blessing
> and in regards to previously published algorithms.
Ah but the technology made for these "contests" can be used on the
real deal.
> I'm not sure if early knowledge about DES and banking (PIN numbers,
> data stored on magnetic swipe or smartcards) might of also been
> affected. I don't know much how was reverse engineered verses
> analyzing published documentation (from X9, NIST, SWIFT, ISO, IBM,
> etc.)
In some states single DES is still used for electronic pads...
> The US copyright/criminal law has no bearing on publishing or
> conferences outside of USA.
Ah but they may limit the *import* of such papers.
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
Comment: Key at: http://tomstdenis.home.dhs.org/key.asc
iQA/AwUBOux6mQULrT+pXe8cEQL93gCfVLaD6A7A7hM3HDK1C9RimAAmYEAAn3Sk
kr0caFjdAU+QdwP2BBRp9XH1
=DxR5
=====END PGP SIGNATURE=====
------------------------------
Subject: Re: Secure Digital Music Initiative cracked?
From: [EMAIL PROTECTED] (Xcott Craver)
Date: Sun, 29 Apr 2001 20:37:57 GMT
William Hugh Murray <[EMAIL PROTECTED]> wrote:
>
>Of course, Napster is not a broadcaster; it is more an indexing and
>directory service. While it is questionable why or that it needs one,
>and while it has tried to negotiate one, it does not have a license from
>the publishers. one might conclude that the industry has more interest
>in trying to outlaw what Napster does than in making money from it.
Evidence for this is the amount of time that has passed
between now and back when the web first became popular.
It was quite long ago that entertainment companies dreamed
out loud about delivering music and video over the Internet.
It might not have been feasible in 1995, but they could have
been considerably more prepared when Napster became popular.
In the end, it seems they have been dragged to online delivery
models kicking and screaming, finally announcing their own
service after years of trying to quash the whole idea.
Even then it's just an announcement on their part, total
vaporware, perhaps just a ploy to counter Napster's claims
that the industry wasn't meeting consumers' needs.
-S
------------------------------
Subject: Re: Censorship Threat at Information Hiding Workshop
From: [EMAIL PROTECTED] (Xcott Craver)
Date: Sun, 29 Apr 2001 20:44:22 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>> In a similar
>> vein, wouldn't researches in number theory on efficient
>> methods of factoring that could defeat certain patented
>> PK algorithms also be considered criminal acts?
>
>Most likely. I would bet in the next 10 years all forms of
>cryptanalysis will come into the hotlight.
When the EFF built a DES cracker, some congressman was quoted
as saying that their actions could "only help criminals."
>Tom
-S
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: Sun, 29 Apr 2001 21:15:17 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Xcott Craver" <[EMAIL PROTECTED]> wrote in message
news:G2%G6.2641$[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >> In a similar
> >> vein, wouldn't researches in number theory on efficient
> >> methods of factoring that could defeat certain patented
> >> PK algorithms also be considered criminal acts?
> >
> >Most likely. I would bet in the next 10 years all forms of
> >cryptanalysis will come into the hotlight.
>
> When the EFF built a DES cracker, some congressman was quoted
> as saying that their actions could "only help criminals."
Yes but it wasn't made illegal. Technically if some anal DA wanted
to they could file charges against the EFF for this device.
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
Comment: Key at: http://tomstdenis.home.dhs.org/key.asc
iQA/AwUBOuyEXgULrT+pXe8cEQIPMACfZVRU2Q/mTMlYqKvLiatTJVPaZIIAnA5X
GNNMBMSi33ut+2121IWaBb6Y
=cr/I
=====END PGP SIGNATURE=====
------------------------------
From: CrapMail Bait <[EMAIL PROTECTED]>
Subject: EC encrypt/decrypt
Date: Sun, 29 Apr 2001 21:22:44 GMT
Pardon my bothering you folk. I'm new to this NG and I'd have to say
that those who contribute are doing everyone a favour in spreading the
knowledge, keep it up!
I've implemented lots of finite integer crypto from the ground up.
I'd like to start putting together some EC (aka ECC) algorithms. Over
F_p and F_{2^n} fields.
1. How do you map an arbitrary input (eg. digest hash, session key) to
an elliptical point on a given curve? I hope there's something more
clever than randomly augmenting the first 8 bits until you find a
match.
2. What are the legal barriers to using EC crypto? GPL vs. BSD (aka.
non-profit vs. truly free)? Public vs. Royalties (aka. truly free vs.
slavery)?
Thanks a bunch.
Jean-Luc Cooke
Carleton Univ. (Canada, if you haven't guessed with the spelling)
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.arch.arithmetic
Subject: Re: GF(2^m)
Date: Sun, 29 Apr 2001 21:28:23 GMT
In article <9cgomr$7lc$[EMAIL PROTECTED]>
"Andre" <[EMAIL PROTECTED]> writes (on sci.math):
>What's the main advantage of Galois Field operation compared to Integer
>operation?
>And, how does GF operation use in Cryptosystem?
>Your regards!
GF(2^m) operations can be implemented without
worrying about carries. For example, if you want to add
two elements of GF(2^100) on a 32-bit machine
(so each operand uses CEIL(100/32) = 4 words),
you need only four exclusive OR (plus loads and stores).
Adding two values modulo a 100-bit prime p would require
one add, three adds with carry. Then you check whether
the sum is >= p, possibly subtracting p.
The operation modulo p is about three times as costly.
Many common architectures support 32 x 32 -> 64
integer multiply (with carries) but few support
32 x 32 -> 64 GF multiply. However special-purpose
hardware for a GF multiply is simpler than for an integer multiply.
There was a recent sci.crypt series on GF mults.
The GF(2^m) squaring is simple.
There is only one field of sise GF(2^m).
If somebody breaks the discrete logarithm problem over GF(2^m),
you must switch to another size m,
changing the lengths of many messages.
If somebody breaks the discrete logarithm problem over GF(p),
you may be able to use another p of the same size.
--
The 21st century is starting after 20 centuries complete,
but we say someone is age 21 after 21 years (plus fetus-hood) complete.
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.arch.arithmetic
Subject: Re: GF(2^m)
Date: Sun, 29 Apr 2001 21:34:35 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Peter L. Montgomery" <[EMAIL PROTECTED]> wrote in
message news:[EMAIL PROTECTED]...
> In article <9cgomr$7lc$[EMAIL PROTECTED]>
> "Andre" <[EMAIL PROTECTED]> writes (on sci.math):
> >What's the main advantage of Galois Field operation compared to
> >Integer operation?
> >And, how does GF operation use in Cryptosystem?
> >Your regards!
>
> GF(2^m) operations can be implemented without
> worrying about carries. For example, if you want to add
> two elements of GF(2^100) on a 32-bit machine
> (so each operand uses CEIL(100/32) = 4 words),
> you need only four exclusive OR (plus loads and stores).
> Adding two values modulo a 100-bit prime p would require
> one add, three adds with carry. Then you check whether
> the sum is >= p, possibly subtracting p.
> The operation modulo p is about three times as costly.
>
> Many common architectures support 32 x 32 -> 64
> integer multiply (with carries) but few support
> 32 x 32 -> 64 GF multiply. However special-purpose
> hardware for a GF multiply is simpler than for an integer multiply.
> There was a recent sci.crypt series on GF mults.
> The GF(2^m) squaring is simple.
I typically implement GF mults via tables or shift/conditional xors.
How is squaring simple in GF?
> There is only one field of sise GF(2^m).
> If somebody breaks the discrete logarithm problem over GF(2^m),
> you must switch to another size m,
> changing the lengths of many messages.
> If somebody breaks the discrete logarithm problem over GF(p),
> you may be able to use another p of the same size.
Ah GF is really only good for block ciphers and ECC. (And correction
codes, random bit generators, fun)
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
Comment: Key at: http://tomstdenis.home.dhs.org/key.asc
iQA/AwUBOuyI2AULrT+pXe8cEQLMdwCgtKF7r7xMrMiheR9dapojtNMAuUMAoIFg
R/fthYocGAFX0y8DyWTqp6Ab
=/jhv
=====END PGP SIGNATURE=====
------------------------------
From: CrapMail Bait <[EMAIL PROTECTED]>
Subject: Re: Announcing A New Rijndael Encryption Algorithm Implementation
Date: Sun, 29 Apr 2001 21:36:39 GMT
"Ryan M. McConahy" wrote:
<snip>
> Yeah. I believe you. NOT! I use PGP. I have compiled my own
> version. No backdoors. Well,
> as far as I know... and many people have looked over the 2.6.3
> source code.
Did you hand assemble the compiler....
JLC
------------------------------
From: "Jack Lindso" <[EMAIL PROTECTED]>
Subject: Re: RSA BRUTE FORCE
Date: Mon, 30 Apr 2001 00:40:23 +0200
Like John said would you try this one :
3081 8902 8181 00C6 6F55 3283 E3D8 EF1D 77E6 01A3 6316 506A DB81 4885 FA2C
A299 AF9C E1CA D65D 05A1 B861 8AD1 A778 901B 445E AA99 FC1D 2683 1E99 8906
D684 4DCE B859 E7F5 3281 AB9C 3169 8413 BD3A A1A8 D26D CDE3 AB9C BCF5 808A
5EF1 40CC 81D0 B491 59C9 ED22 519A D12F 1361 BF52 0D37 EC42 2FB4 59DF 06F5
43EC 0A1E E3AD 4F6E 1FA4 7E88 4437 B902 0301 0001
"it's a properly-formed DER encoding of an RSA public key" posted her by
someone, in a previous
post ...........
--
Anticipating the future is all about envisioning the Infinity.
http://www.atstep.com
====================================================
"Erictim" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> THERE ARE SOME THINGS I DON'T UNDERSTAND ABOUT THE RSA ALGORITHM. MY
> UNDERSTANDING IS THAT RSA GENERATES A LARGE NUMBER (N) WHICH HAS ONE AND
ONLY
> ONE PAIR OF FACTORS(P AND Q) SECURITY IS DEPENDANT ON DIFFICULTY OF
FACTORING
> LARGE NUMBERS.
>
> WHY IS FACTORING SO DIFFICULT? IF THEIR IS ONLY ONE PAIR OF FACTORS THAN
> COMPUTERS ARE LIKELY FAST ENOUGH TO RUN A GREATER THAN,LESS THAN BRUTE
FORCE
> ATTACK?
>
> STEPS
>
> 1) GET LARGE NUMBER (N)
>
> 2) USE GREATER THAN,LESS THAN BRUTE FORCE ATTACK TO FIND THE LENGTH
> POSSIBILITIES OF THE FACTORS FOR (N)--(P AND Q)
>
> 3) USE GREATER THAN,LESS THAN BRUTE FORCE ATTACK TO FIND EACH POSSIBLE
PAIR OF
> DIGITS IN THE FACTORS(P AND Q)
>
> 4) REPEAT STEPS 1 TO 3 UNTIL FACTORS ARE FOUND
>
> BRUTE FORCE GREATER THAN,LESS THAN ATTACK
>
> TEST EACH POSSIBLE PAIR OF DIGITS BY BEGINNING AT THE LEFT SIDE OF THE
NUMBER.
> FILL ALL DIGITS TO THE RIGHT OF THE TEST PAIR WITH 9's. RUN THE
ALGORITHM(SUCH
> AS MULTIPLY THE TWO DIGITS). TEST IF THE RESULT IS GREATER THAN OR LESS
THAN
> THE NUMBER BEING COMPARED TO.
>
> EXAMPLE
>
> Y^X = Z(Y AND Z ARE KNOWN)
> 2^X=3.1691265E29
>
> to find how large X is:
> 2^999=too large
> 2^99=too large
> 2^9=too small
> X MUST BE 2 DIGITS SINCE THE MAXIMUM FOR ONE DIGIT IS TOO SMALL AND THE
MAXIMUM
> FOR 2 DIGITS IS TOO LARGE
>
> too find the digits:
> 2^99=too large
> 2^89=too small
> 2^79=too small
> THE FIRST DIGIT MUST BE A 9, BECAUSE EVERYTHING UNDER 9 IS TOO SMALL
>
> 2^99=too large
> 2^98=is equal
> 2^97=too small
> X IS 98
>
> OF COURSE THIS COULD BE DONE WITH PAIRS OF NUMBERS.
>
> P * Q = N
>
> (0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9)
> (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9)
> (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9)
> (3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9)
> (4,4) (4,5) (4,6) (4,7) (4,8) (4,9)
> (5,5) (5,6) (5,7) (5,8) (5,9)
> (6,6) (6,7) (6,8) (6,9)
> (7,7) (7,8) (7,9)
> (8,8) (8,9)
> (9,9)
>
> SWITCHING THE ORDER OF EACH PAIR LEAVES A TOTAL OF 110 PAIRS OF NUMBERS.
BY
> PLUGGING THESE PAIRS INTO FACTORS(P AND Q) AND REPLACING THE DIGITS TO THE
> RIGHT WITH 9's A GREATER THAN,LESS THAN BRUTE FORCE ATTACK COULD BE USED
TO
> FIND FACTORS(P AND Q) IF (P) AND (Q) WERE BOTH 300 DIGITS LONG THERE
WOULD BE
> 33000 POSSIBLE COMBINATIONS. NOTE: IT IS POSSIBLE FOR SOME DIGITS TO
HAVE
> MORE THAN ONE PAIR WHICH LOOK ACCURATE. IT IS ALSO POSSIBLE TO
SIGNIFICANTLY
> REDUCE THE AMOUNT OF NUMBER PAIRS NEEDED TO CHECK BY "SKIPPING"(FOR
EXAMPLE:
> IF THE PAIR (5,9) IS TESTED AND FOUND TO BE TOO SMALL THEN ALL NUMBERS
BELOW
> (5,9)--SUCH AS (1,2)-(3,4)-(5,6)...-- DO NOT NEED TO BE TESTED. IT IS NOT
> LIKELY THAT MORE THAN 40000 SCENARIOS WOULD NEED TO BE TESTED. I ASSUME
> COMPUTERS ARE SOMEWHAT FAST AT MULTIPLICATION. I ASSUME A TYPICAL
PROCESSOR
> COULD TEST AT LEAST ONE SCENARIO EACH SECOND. IF THOSE TWO ASSUMPTIONS
ARE
> CORRECT THEN A SINGLE PROCESSOR COULD FIND THE FACTORS IN 11-12 HOURS. A
> THOUSAND PROCESSORS WOULD HAVE THE FACTORS IN LESS THAN A MINUTE. THIS
DOESN'T
> SOUND VERY SECURE. AM I RIGHT? OR AM I WRONG AND STUPID?
------------------------------
From: CrapMail Bait <[EMAIL PROTECTED]>
Subject: Re: DSA in GF(2^W)?
Date: Sun, 29 Apr 2001 21:56:01 GMT
Tom St Denis wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Is it possible to setup DSA for use in GF(2^W) instead of Z*p ?
>
> I.e
>
> let p be a 1024-bit irreducible polynomial
> let q be a a large factor of 2^1024 - 1
> let g be a generator such that g^((2^1024 - 1) / q) != 1
>
> What current attacks are there against GF(2^K) Discrete Log type
> problems? I will go look through my Eurocrypt collection.... any
> pointers would be nice :-)
> - --
> Tom St Denis
> - ---
> http://tomstdenis.home.dhs.org
ECDSA does this nearly. See PLM's responce to the GF(2^m) thread.
Peter's words are sage.
JLC
------------------------------
From: CrapMail Bait <[EMAIL PROTECTED]>
Subject: Re: DSA in GF(2^W)?
Date: Sun, 29 Apr 2001 21:57:47 GMT
CrapMail Bait wrote:
^^^^^^^^
My brother likes fixing my netscape settings to bug me. I appologise
to everyone here. Let me step off and slap him.
JLC
------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Subject: Re: DSA in GF(2^W)?
Date: Sun, 29 Apr 2001 21:59:18 GMT
CrapMail Bait wrote:
>
> CrapMail Bait wrote:
> ^^^^^^^^
>
> My brother likes fixing my netscape settings to bug me. I appologise
> to everyone here. Let me step off and slap him.
>
> JLC
test
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: DSA in GF(2^W)?
Date: Sun, 29 Apr 2001 22:01:01 GMT
"CrapMail Bait" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> >
> > Is it possible to setup DSA for use in GF(2^W) instead of Z*p ?
> >
> > I.e
> >
> > let p be a 1024-bit irreducible polynomial
> > let q be a a large factor of 2^1024 - 1
> > let g be a generator such that g^((2^1024 - 1) / q) != 1
> >
> > What current attacks are there against GF(2^K) Discrete Log type
> > problems? I will go look through my Eurocrypt collection.... any
> > pointers would be nice :-)
> > - --
> > Tom St Denis
> > - ---
> > http://tomstdenis.home.dhs.org
>
> ECDSA does this nearly. See PLM's responce to the GF(2^m) thread.
> Peter's words are sage.
My understanding is that all EC algorithms are based on multiply a secret
key against a base point? Like you can do DH and ElGamal on EC systems.
DSA involves discrete exponentiation. While I know DSA exists on EC systems
would it be the same thing as DSA in Z*p?
Tom
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
