Cryptography-Digest Digest #520, Volume #14       Mon, 4 Jun 01 23:13:01 EDT

Contents:
  Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Paul Pires")
  Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large Primes 
("Tom St Denis")
  Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
  Re: Def'n of bijection ("Robert J. Kolker")
  Re: Def'n of bijection ("Tom St Denis")
  Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY)
  Re: Def'n of bijection (SCOTT19U.ZIP_GUY)
  Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P. Dulles / AKA 
Loki) (Eric Lee Green)
  Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P. Dulles / AKA 
Loki) (Eric Lee Green)
  Re: RSA's new Factoring Challenges: $200,000 prize. (Sergei Lewis)
  Re: Fast 8-bit mults on smartcards (Mark Wooding)
  Re: about DH parameters & germain primes (Mark Wooding)
  Re: Keyed hash functions (Mark Wooding)
  Re: BBS implementation (Mark Wooding)
  Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P.   ("Trevor L. 
Jackson, III")
  Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P. ("Trevor L. 
Jackson, III")

----------------------------------------------------------------------------

From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Mon, 4 Jun 2001 18:03:52 -0700


Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
> : news:[EMAIL PROTECTED]...
> :> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
>
> [BICOM vs Rijndael in CTR mode]
>
> :> :> :> He explained it - you just didn't understand the explanation.
> :> :>
> :> :> : What explanation?  All he does is flame me.
> :> :>
> :> :> This sort of thing, repeated several times now:
> :> :>
> :> :> DS> And you never anwsered the FACT that a one byte ouput file
> :> :> DS> from CTR mode (though you have no working program) would imediately
> :> :> DS> lead an attacker to realize that the input file could only have
> :> :> DS> come from 1 of 256 possible messages. With BICOM you have many
> :> :> DS> many more messages. That alone makes it more secure.
> :>
> :> [snip]
> :>
> :> : His logic is flawed.  He states a feature of BICOM then assumes its a
> :> : security bonus.
> :>
> :> Knowledge that a message comes from a set of billions of possible key
> :> selected messages, rather than a set of 256 possible key selected messages
> :> *is* a feature that has an immediate impact on security.
> :>
> :> If you can narrow the plaintext down to one of 256 possibilities, then
> :> that is already a significant leak of information about the message
> :> contents.
>
> : OTP encrypted message.
>
> : C=1101111010001
>
> : What is P?
>
> : (How long must this go on?)
>
> I don't know:
>
> Maybe until you realise that an OTP doesn't have perfect secrecy if it's
> dealing with finite files, and converting them to cyphertexts of the same
> length as the plaintexts?
> --
Ehrr?  Why not? Length of Pt = Ct length = key length of random origin, only used once.
It seems to me that that a Ct could be from any possible Plaintext of exactly
the same size. Are you saying that just leaking the size is a lapse in perfect
secrecy? Even if it was compressed, the plaintext is still the same size as the
ciphertext. It's just that the plaintext is now a compressed volume. What am I
missing?

Paul
> __________
>  |im |yler  [EMAIL PROTECTED]  Home page: http://alife.co.uk/tim/




------------------------------

From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large 
Primes
Date: Tue, 05 Jun 2001 01:12:20 GMT


"Gregory G Rose" <[EMAIL PROTECTED]> wrote in message
news:9fhb44$[EMAIL PROTECTED]...
> In article <ebvtZ6S7AHA.201@cpmsnbbsa09>,
> Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> >make things easy, RSA looks easy enough, once the Wide Trail Strategy has
> >been developed it makes development fairly straight forward. OTOH
>
> What is this Wide Trail Strategy?

I believe the term was invented by J.Daemen.

The idea is to have small (or possible just efficient at a cost in security)
sboxes but to try and make as many of them active w.r.t. to an attack as
possible.

See the Serpent, Rijndael, Noekeon, Crypton, Twofish or Khazad designs for
example.

Tom



------------------------------

From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Tue, 05 Jun 2001 01:13:28 GMT


"Paul Pires" <[EMAIL PROTECTED]> wrote in message
news:AfWS6.11163$[EMAIL PROTECTED]...
>
> Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> >
> > : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
> > : news:[EMAIL PROTECTED]...
> > :> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > :> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
> >
> > [BICOM vs Rijndael in CTR mode]
> >
> > :> :> :> He explained it - you just didn't understand the explanation.
> > :> :>
> > :> :> : What explanation?  All he does is flame me.
> > :> :>
> > :> :> This sort of thing, repeated several times now:
> > :> :>
> > :> :> DS> And you never anwsered the FACT that a one byte ouput file
> > :> :> DS> from CTR mode (though you have no working program) would
imediately
> > :> :> DS> lead an attacker to realize that the input file could only
have
> > :> :> DS> come from 1 of 256 possible messages. With BICOM you have many
> > :> :> DS> many more messages. That alone makes it more secure.
> > :>
> > :> [snip]
> > :>
> > :> : His logic is flawed.  He states a feature of BICOM then assumes its
a
> > :> : security bonus.
> > :>
> > :> Knowledge that a message comes from a set of billions of possible key
> > :> selected messages, rather than a set of 256 possible key selected
messages
> > :> *is* a feature that has an immediate impact on security.
> > :>
> > :> If you can narrow the plaintext down to one of 256 possibilities,
then
> > :> that is already a significant leak of information about the message
> > :> contents.
> >
> > : OTP encrypted message.
> >
> > : C=1101111010001
> >
> > : What is P?
> >
> > : (How long must this go on?)
> >
> > I don't know:
> >
> > Maybe until you realise that an OTP doesn't have perfect secrecy if it's
> > dealing with finite files, and converting them to cyphertexts of the
same
> > length as the plaintexts?
> > --
> Ehrr?  Why not? Length of Pt = Ct length = key length of random origin,
only used once.
> It seems to me that that a Ct could be from any possible Plaintext of
exactly
> the same size. Are you saying that just leaking the size is a lapse in
perfect
> secrecy? Even if it was compressed, the plaintext is still the same size
as the
> ciphertext. It's just that the plaintext is now a compressed volume. What
am I
> missing?

I would say a very long acid trip.  :-)  (you'd have to be on one to make
sense of their arguments)

Tom



------------------------------

From: "Robert J. Kolker" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Mon, 04 Jun 2001 21:16:08 -0400



Tom St Denis wrote:

>
> Um no offense but please keep up with the posts.  I already admitted I was
> wrong and was corrected 23 times already.

Tail end Bob apologizes.

Bob Kolker



------------------------------

From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Tue, 05 Jun 2001 01:36:41 GMT


"Robert J. Kolker" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
>
> >
> > Um no offense but please keep up with the posts.  I already admitted I
was
> > wrong and was corrected 23 times already.
>
> Tail end Bob apologizes.

No harm done.  I was wrong originally.  It's just getting very boring to
here "no no no you're wrong" so many times...

Tom



------------------------------

From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: 5 Jun 2001 01:43:59 GMT

[EMAIL PROTECTED] (Paul Pires) wrote in
<AfWS6.11163$[EMAIL PROTECTED]>: 

>
>Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
>> Tom St Denis <[EMAIL PROTECTED]> wrote:
>>
>> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
>> : news:[EMAIL PROTECTED]... 
>> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
>> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
>> : news:[EMAIL PROTECTED]...
>> :> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
>> :> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
>>
>> [BICOM vs Rijndael in CTR mode]
>>
>> :> :> :> He explained it - you just didn't understand the explanation.
>> :> :>
>> :> :> : What explanation?  All he does is flame me.
>> :> :>
>> :> :> This sort of thing, repeated several times now:
>> :> :>
>> :> :> DS> And you never anwsered the FACT that a one byte ouput file
>> :> :> DS> from CTR mode (though you have no working program) would
>> :> :> imediately DS> lead an attacker to realize that the input file
>> :> :> could only have DS> come from 1 of 256 possible messages. With
>> :> :> BICOM you have many DS> many more messages. That alone makes it
>> :> :> more secure. 
>> :>
>> :> [snip]
>> :>
>> :> : His logic is flawed.  He states a feature of BICOM then assumes
>> :> : its a security bonus.
>> :>
>> :> Knowledge that a message comes from a set of billions of possible
>> :> key selected messages, rather than a set of 256 possible key
>> :> selected messages *is* a feature that has an immediate impact on
>> :> security. 
>> :>
>> :> If you can narrow the plaintext down to one of 256 possibilities,
>> :> then that is already a significant leak of information about the
>> :> message contents.
>>
>> : OTP encrypted message.
>>
>> : C=1101111010001
>>
>> : What is P?
>>
>> : (How long must this go on?)
>>
>> I don't know:
>>
>> Maybe until you realise that an OTP doesn't have perfect secrecy if
>> it's dealing with finite files, and converting them to cyphertexts of
>> the same length as the plaintexts?
>> --
>Ehrr?  Why not? Length of Pt = Ct length = key length of random origin,
>only used once. It seems to me that that a Ct could be from any possible
>Plaintext of exactly the same size. Are you saying that just leaking the
>size is a lapse in perfect secrecy? Even if it was compressed, the
>plaintext is still the same size as the ciphertext. It's just that the
>plaintext is now a compressed volume. What am I missing?
>
>Paul


 What your missing is that we are not talking about an OTP What this
whole thing is about. Is the comparing of BICOM to AES in CTR mode.
Notice both use 256bit key RIJNDEAL. The question was then posed
what if one gets a single byte cipher text output file. Yes it could
be compressed and then run through CTR mode. Tom has stated that
if one recieved such a file he realizes it could be any from a set
of 256 messages. There may have been millions upon millions of
possible plaintext messages. But by getting one byte out you have
limited it to one of 256 messages. Tom is convenced this is very
secure since. In his mind CTR is very secure and like any Snake
Oil Saleman does a tap shoe dance saying it an OTP and then shuts
brain off. In BICOM if you get a single byte out. You still have
2**128 different possible input messages. Yet Tom thinks that
means nothing and 1 out of 256 is total security in his mind.

 Other threads on Uicity distance where he offered to bet 100 dollars
have gone no where. It seems he had no real understanding of the
basics of ecryption compression and entropy. Maybe he has been smoking
to much dope and his brain is a little fried.



David A. Scott
-- 
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
        http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
 made in the above text. For all I know I might be drugged or
 something..
 No I'm not paranoid. You all think I'm paranoid, don't you!


------------------------------

From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Def'n of bijection
Date: 5 Jun 2001 01:51:31 GMT

[EMAIL PROTECTED] (Tom St Denis) wrote in 
<JIWS6.28419$[EMAIL PROTECTED]>:

>
>"Robert J. Kolker" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>>
>>
>> Tom St Denis wrote:
>>
>> >
>> > Um no offense but please keep up with the posts.  I already admitted I
>was
>> > wrong and was corrected 23 times already.
>>
>> Tail end Bob apologizes.
>
>No harm done.  I was wrong originally.  It's just getting very boring to
>here "no no no you're wrong" so many times...

  Like I stated before when you jumped on him you never stated
you where wrong till then. I know your not using real logic or
Tim would have got through to you. So it must be you base you
facts on the people who spout them. Which person made you see
the error of your ways. 



David A. Scott
-- 
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
        http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
 made in the above text. For all I know I might be drugged or
 something..
 No I'm not paranoid. You all think I'm paranoid, don't you!


------------------------------

From: [EMAIL PROTECTED] (Eric Lee Green)
Crossposted-To: 
alt.privacy,alt.security,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P. Dulles / 
AKA Loki)
Reply-To: [EMAIL PROTECTED]
Date: Tue, 05 Jun 2001 02:22:18 GMT

=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1

On Mon, 4 Jun 2001 00:46:17 +0100, EE Support <support_removethis@evidence-
eliminator.com> wrote:
>re this nonsense "Loki / P. Dulles" character and phony signature block:
>>--
>>Loki
>>----
>>The Truth about Evidence Eliminator:
>>http://badtux.org/eric/editorial/scumbags.html
>
>proven lies, misinformation and propaganda

I am still waiting for any employee of Robin Hood Software to send me
EMAIL detailing inaccurate information on my pages. I guarantee that I
will correct any inaccurate information in a timely manner (within 72
hours). 

I expect to receive an EMAIL from the EE guys about the same time
that Canada becomes the 51st state of the United States.

>>http://www.radsoft.net/resources/software/reviews/ee/07.htm
>
>cranky, useless rantings of no worth whatsoever
>What a pathetic, failed load of rubbish.
>
>Yet another phony 'character' begins to whine to the Anti-Evidence
>Eliminator tune of "Eric Lee Green."

Interestingly, my page and the Radsoft page both originated independently
at the same time. I learned of Radsoft from the administrator of
Ellipse.to, who was spammed by the Evidence Eliminator guys, and by that
time the Radsoft pages were already up. Radsoft has a pretty decent
reputation in the DOS and Windows world, going back for years (don't
take my word for it, go do a Google search). Radsoft is not some phony
"character", the proprieter of Radsoft is a well-known figure in Windows
development circles and has been for years (unlike the two young men who
are Robin Hood Software, who appeared from nowhere a little over a year ago
flogging their Visual BASIC bloatware). 

>"Eric Lee Green" and his phony followers have been repeatedly exposed for
>ruining newsgroups with proven lies and propaganda. They wish to dissuade
>you from using the world's #1 hard disk cleaning utility, Evidence
>Eliminator.

As mentioned before, I haven't any opinion of Evidence
Eliminator. However, I do have an opinion of Robin Hood
Software. These scumbags (my opinion) spam, libel people on their web
site, and have violated my copyrights on materials that they obtained
from my web site, in violation of both U.S. law and U.K. law. In other
words, they are criminals. They rely upon the fact that they're on the
opposite side of the pond to allow them to libel and defame
U.S. citizens at will.  You will notice that they do not make a single
defamatory statement about any U.K. citizen. That's because they don't
want to get sued in a UK court. If they are so hated by "anti-privacy"
people, why is it that they only seem to be hated by U.S. citizens and
not by U.K. citizens? (Note: That's not true, BTW, there are many UK
citizens who have spoken out publically about these scumbags, but
you'd never know it by reading the EE pages or EE postings).

>"Loki" is introduced as a proven source of "Eric Lee Green" lie-supporting
>dis-information about Evidence Eliminator. A suitable collection of lies,
>mis-information and propaganda is included from "Loki" below as "Loki" tries
>to persuade you not to use the best hard disk cleaner you can get.

Yawn. Still waiting for a single lie to be "proven". BTW, "Loki" is not
me. I'm no cypherpunk. I have barely figured out how to use GnuPG to
sign my messages, and personally have no use for anonymity. My life is
an open book. A little bit of digging (heck, a little use of "whois"!) will
net you my home phone number, my address, my current employer (who is
*NOT* Enhanced Software Technologies Inc., unlike what the twits at EE
tell you), etc. A little bit of "Google" will show you my employment
history for the past 7 or 8 years. Heck, my resume may even still be in
the Google cache. 

>======================================================================
>Look at the nonsense above. This is proof that you need Evidence Eliminator.
>Newbie warning: This message is a collection of Propaganda. Propaganda is
>false information, deliberately spread. This is propaganda designed to stop
>you using Evidence Eliminator and therefore leave your hard disk open to
>forensic analysis by the police or FBI or snoops. False messages are
>wide-spread in the privacy / security newsgroups. To read a short-list of
>false information promoted by "Eric Lee Green" about Evidence Eliminator
>software, click the URL below:
>http://www.evidence-eliminator.com/dis-information.shtml
>======================================================================

I would stake my reputation against that of spammers from Nottingham
UK any time of the day. Don't be fooled by their hand-waving and
lies. Research it for yourself. Go to http://www.google.com and do a
search for "Eric Lee Green". You will find that I have been an active
USENET participant for over ten years and was responsible for porting
several pieces of the USENET software to the Amiga computer
(R.I.P). Go do a search for "Andy Churchill" or "Robert Ride". You'll
find that they appeared out of nowhere at the beginning of 2000,
selling their Visual BASIC bloatware, but otherwise don't seem to have
ever existed before their "Evidence Eliminator" days. So who do you
believe -- someone who has a reputation on the USENET for saying it
like he sees it, and has been doing that for over ten years, or some
criminal spammers from the UK? (Use of my copyrighted materials
obtained from my web site for profit IS a crime, guys!).

Then go to http://www.badtux.org/eric/editorial/scumbags.html to get
the rest of the scoop. And if you're feeling bored, well,
http://www.nimitz.net/randy/ has an interesting spoof of these
infant's "reasoning".


=====BEGIN PGP SIGNATURE=====
Version: GnuPG v1.0.5 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE7HD/o3DrrK1kMA04RAmKMAJ0aCdWVgix2N7J7cV5kRQ/2EG3HzgCeNPaR
1GBR4U+kDCjzqA9zRBmFjV4=
=KlHB
=====END PGP SIGNATURE=====

------------------------------

From: [EMAIL PROTECTED] (Eric Lee Green)
Crossposted-To: 
alt.privacy,alt.security,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P. Dulles / 
AKA Loki)
Reply-To: [EMAIL PROTECTED]
Date: Tue, 05 Jun 2001 02:31:40 GMT

=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1

On Mon, 04 Jun 2001 13:21:19 GMT, Tony L. Svanstrom <[EMAIL PROTECTED]> wrote:
>EE Support <[EMAIL PROTECTED]> wrote:
>
>> We estimate 50% at least of posts on this newsgroup are fakes designed to
>> remove your Internet privacy.
>
>"We're right, and the ones that say that we're wrong are lying."
>
>You sure you guys aren't working for the gov? hehe

You laugh, but I can't find any evidence of Andy Churchill or Robert
Ride existing prior to 16 months ago, when they started flogging
Evidence Eliminator in the newsgroups. They don't have a phone number
listed in the phone book, they don't have a business address (other
than a "mail drop" in London), and the address they've given as their
"real" business address appears to be a residential duplex in a
residential neighborhood of Nottingham. The notion that they are
stooges of various Three Letter Agencies out to discredit the notion of
security software seems less incredible in that light.

Actually, I don't think that's true. I think these are a couple of young
men who have too much arrogance and testosterone flowing thru their
veins and who haven't had enough experience under their belt to learn a
bit of common sense. I actually feel a bit sorry for them. Every time they
open their mouth, they prove their immaturity and lack of trustworthiness.
I don't feel sorry enough for them to take down 
http://badtux.org/eric/editorial/scumbags.html though. They made it 
personal, and that page stays up costing them sales until the day they
remove my picture and any reference to me from their web pages. 
I'm not selling anything. They are. They're the ones losing money every
day because people do a Google search and find out the truth. 


=====BEGIN PGP SIGNATURE=====
Version: GnuPG v1.0.5 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE7HEIb3DrrK1kMA04RAos9AKCYwl/I3fW/bbAqxJzwM94DUskWGACferTR
Qr2foxpia+Q6msSzr6tdJ3g=
=bdm9
=====END PGP SIGNATURE=====

------------------------------

From: Sergei Lewis <[EMAIL PROTECTED]>
Subject: Re: RSA's new Factoring Challenges: $200,000 prize.
Date: Mon, 04 Jun 2001 16:04:00 +0100

Michael Brown wrote:
> > I concur.  What I wonder, not having studied this algorithm yet,
> > is the rate of growth of work-per-box as the problem size is
> > increased.
> With a decent implementation of the algorithm (see below), the number of
> operations per box should remain much the same (actual number of instructions
> depends on instruction set).

Hm. I was bored over the weekend so wrote a quick hack to naively
implement the space-hungry reverse adder logic part of Michael's
algorithm. It's on http://members.tripod.co.uk/Folken/f.c

To sum up my understanding of the whole thing:

You need O (((log n)^2)/2) space. For RSA, that's in the megabytes
rather than the gigabytes unless I'm missing something obvious ^^;;

You end up with boxes of the form
 ?
0 ?
 1
which can't be reduced further trivially, one per bit set in the product
you are factoring.

You can set one bit arbitrarily for exactly one of these, since you know
the two factors are different and exactly one bit is set; this on its
own doesn't help resolve all of them.

Deductions of the form "bit x cannot be set in both factors because of
box y", "bit x must be set in both factors because of box y", and "bit x
must be set in neither factor because of box y" can be used to resolve
these, as Michael's page describes, but you need some really nasty hairy
logic to do this. If I feel like playing again sometime, I might try my
hand at some ^^;;

If I understand correctly, it is Michael's assertion that such
deductions, in combination with the one bit of information you may set
arbitrarily without loss of generality, are enough to deduce the
factors.

There are at most 8*(((log n)^2)/2)+2(log n) bits of information
required for the algorithm to operate. The algorithm works in multiple
passes, interleaving the reverse adder logic with deductions about the
factors as described above.

Since the algorithm halts as a result of a pass that does not set at
least one bit of information, this is also an upper bound on the number
of operations performed.

Hope all that helps someone ^^;; if I've misunderstood something,
Michael, please correct me ^-^

-- 
Sergei Lewis - http://members.tripod.co.uk/~Folken
   "I'm not falling - this is how I fly.."

------------------------------

From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Fast 8-bit mults on smartcards
Date: 4 Jun 2001 10:50:44 GMT

Robert Harley <[EMAIL PROTECTED]> wrote:

> What's wrong with it?  The parentheses around p(x) indicate "the ideal
> generated by".  Seems fine to me.

I think, if you'll pardon the pun, that notation is far from ideal.
Putting parentheses around things to change their meanings causes all
sorts of horrible ambiguities.  For example, suppose we're working in
F_2[x]: is x (x^3 + 1) just x^4 + x, or is it really the ideal
(x^4 + x) F_2[x] ?

-- [mdw]

------------------------------

From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: about DH parameters & germain primes
Date: 4 Jun 2001 11:39:30 GMT

quequ <[EMAIL PROTECTED]> wrote:

> "If p, (p-1)/2 both prime, then you can just use any
> g you please [other than 0, 1, and -1], and you'll
> get a very large order [at least (p-1)/2]"
> 
> It's right?

Yes, it's right.

> I've tried a 1024bit germain prime P and the generator G set to (P-1)/2. 
> Are these good parameters?

(P - 1)/2 is a bit big.  This won't affect security, but it can affect
performance in some cases.  In your case, I'd choose G = 4, which
definitely has order (P - 1)/2.  At least this way you know exactly what
you're getting.

On the other hand, I don't really believe in Sophie-Germain primes.
They take too long to generate, and I don't see any practical advantage
over Lim-Lee primes.

-- [mdw]

------------------------------

From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Keyed hash functions
Date: 4 Jun 2001 15:46:19 GMT

Tim Tyler <[EMAIL PROTECTED]> wrote:

> Are such "keyed hash functions" recognised as a primitive cryptographic
> type, distint from MACs?

I believe that your idea of a `keyed hash' is attempting to capture what
is usually referred to as a `pseudo-random function family'.  A PRF
family is suitable for use as a MAC.  However, not all MACs are good
PRFs.  (Choose any MAC F; define F'(x) = F(x) || 0 -- this is trivially
distinguishable, but is just as good a MAC as F was.)

To this extent, MACs and PRFs are distinct things.  However, I think
there is a hope (rather than anything better informed) that HMAC with a
decent hash function is a passable PRF.  I suspect that there isn't a
great deal of interest in MACs which definitely aren't PRFs.

> Alternatively, is there any precedent for the use of a MAC in a 
> counter-driven PRNG?

Not that I've seen.

> [Note: I *don't* want to talk about hash(CTR|KEY) schemes]

Very wise.

-- [mdw]

------------------------------

From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: BBS implementation
Date: 4 Jun 2001 13:47:07 GMT

[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:

> How do I know it is not on a short or degenerate cycle?

Because if it is, you've managed to factor the modulus.

-- [mdw]

------------------------------

From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: 
alt.privacy,alt.security,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P.  
Date: Tue, 05 Jun 2001 03:07:30 GMT

Tom St Denis wrote:

> "Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > EE Support wrote:
> >
> > [snip]
> >
> > > proven lies, misinformation and propaganda
> >
> > [snip]
> >
> > > ruining newsgroups with proven lies and propaganda. They wish to
> dissuade
> >
> > [snip]
> >
> > I find the concept of a "proven lie" interesting.  It implies that it is
> > possible to prove a falsehood.  One typically proves truths.  A proof of a
> false
> > proposition would be a remarkable thing.  Where can we get more
> information on
> > this feat of logic?
>
> Proof by contradiction.

Right, but see below.

>
>
> There are a finite number of primes.
>
> Take all primes and form a composite N.  Add one to N.  Now N is not
> divisible by any of the "known" primes.  Thus N+1 is a new prime not in the
> list.  Proof by contradiction.  We proved that "there are finite number of
> primes" is false.

This proves that a statement is false, which not what I supposed.  The statement
"X is proven" typically means "X is proven to be true".  So "proving a lie"
would mean "proving a lie to be true", which is a horse of a different spectrum.


------------------------------

From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET  (P.
Date: Tue, 05 Jun 2001 03:09:11 GMT

JPeschel wrote:

> "Trevor L. Jackson, III" [EMAIL PROTECTED] writes, in part:
>
> >I find the concept of a "proven lie" interesting.  It implies that it is
> >possible to prove a falsehood.  One typically proves truths.  A proof of a
> >false
> >proposition would be a remarkable thing.
>
> Oh, goodness -- you are kidding, right?

Sure, but it beats the EE drivel.  ;-)



------------------------------


** 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
******************************

Reply via email to