Cryptography-Digest Digest #897, Volume #11 Tue, 30 May 00 17:13:01 EDT
Contents:
Re: any public-key algorithm (tomstd)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Adrian Kennard)
Re: new public key? (Mok-Kong Shen)
XTR (was: any public-key algorithm) (Ian Goldberg)
Re: Comments requested: One way function blast() (Andru Luvisi)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Andru Luvisi)
Re: No-Key Encryption (Mok-Kong Shen)
Re: driving me and friends nuts ("Douglas A. Gwyn")
Destroy Al Gore's Presidential Election Campaign .... (Markku J. Saarelainen)
Re: any public-key algorithm ("Eric Verheul")
Re: XTR (was: any public-key algorithm) ("Eric Verheul")
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Andy Dingley)
Re: XTR (was: any public-key algorithm) (Ian Goldberg)
Does it even matter? (tomstd)
Re: Destroy Al Gore's Presidential Election Campaign .... (Roger Schlafly)
Re: Does it even matter? (Andru Luvisi)
Re: encryption without zeros (Paul Koning)
----------------------------------------------------------------------------
Subject: Re: any public-key algorithm
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 30 May 2000 12:09:58 -0700
In article <8h12rl$3i8$[EMAIL PROTECTED]>, "Eric Verheul"
<[EMAIL PROTECTED]> wrote:
>> From what I know in fields theory...
>>
>> GF(2) means modulo 2 math, addtion = xor, mutiplication = and
>> GF(p) means modulo a prime math, a+b mod p, etc.
>> GF(2)^n means modulo a polynomial degree 'n' who's
coefficients
>> are modulo 2
>>
>> So does that make
>> GF(p)^6 means modulo a polynomial of degree 6 who's
coefficients
>> are modulo p?
>Right! An irreducible polynomial, that is.
>For instance Z^6 + Z^3 + 1 if p = 3 or 5 mod 9.
I can be tought, yeehaw.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Adrian Kennard <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Tue, 30 May 2000 20:14:28 +0100
David Boothroyd wrote:
>...
> People cannot be put in jail because they have lost their keys, as
> Ministers have made clear during debate on the bill.
Thats a strong claim.
I can "lose" my keys "at will". I just have to "forget" them.
This gives criminals an easy "get out" from the bill.
There is no way to tell if someone has forgotton something
or is lying, and that is what would be necessary to tell
the difference.
If they *guranatee* no-one is put in jail for losing keys,
then the whole idea of a penalty for not handing over keys is
stupid as they would always have to assume you are telling
the truth when you say they are "Lost/forgotton".
Just explain the basic stpes in proving that I *havent* forgotton
something ?
> Without this bill criminals will get away with it. With it they will
> not. It's a simple as that.
That makes no sense.
--
_ Andrews & Arnold Ltd, 01344 400 000 http://aa.nu/
(_) _| _ . _ _ Professional Voice and Data Systems for Business.
( )(_|( |(_|| ) Gold Certified Alchemists, BT ISDN/ADSL Resellers
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: new public key?
Date: Tue, 30 May 2000 21:26:39 +0200
"G. Orme" schrieb:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > 1. Do you happen to have a good piece of software to calculate the
> > 100 digits of 43rd root of 57? There are special softwares. My point
> > is that the computing job can be very expensive for the proper
> > communication partners if the figures involved are large.
>
> G. I agree the job is difficult, but this is an advantage as it is equally
> difficult for someone to
> crack it by trying different numbers.
But if the legitimate communication partners are also greatly hampered
by the difficulties of computations, then you would have a problem
(of acceptance).
> > 2. For a legitimate user of your system, how is he going to determine
> > the values x and y, given 100 digits that are known to be the x-th
> > root of y?
>
> G. He never has to work this out. Only someone trying to crack the code has
> to work it out, which is very difficult.
>
> G. Users would already have the public keys worked out. They would see a
> public key advertised, and look it up and find the values of x and y. They
> would then recalculate the key to use between them. Let's say for example A
> sends a message to B that is encrypted, and with it he sends the 100 digit
> key which A knows is the first 100 digits of the 43rd root of 57. He then
> knows that the message is encrypted with the first 100 digits the 57th root
> of 43. The initial 100 digit public key is then a way for A to tell B that
> the key is the 57th root of 43. For an eavesdropper to work this out he must
> calculate all possible roots until he finds 43 and 57, then calculate out
> the new key 57th root of 43. If the numbers are large this would take a long
> time.
You said that 'They would see a public key advertised, and look it
up and find the values of x and y.' So there is somewhere a lookup
table that is assumed to be kept by both A and B and not accessible
to the analyst. How big is this lookup table? If it is huge, because
there are many pairs of (x, y) provided, wouldn't you have serious
management problems? What is the order of magnitude of the
number of such pairs in the lookup table that you think is reasonable
for some practical applications (comparable to situations where RSA
is used)?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: XTR (was: any public-key algorithm)
Date: 30 May 2000 19:17:09 GMT
In article <8h0tid$qv4$[EMAIL PROTECTED]>,
Eric Verheul <[EMAIL PROTECTED]> wrote:
>Hey, don't forget XTR now! It has all the computational and
>communicational benefits of ECC (and more) but it's security is based
>on the DL problem in GF(p^6), i.e. a sixth field extension of a basic
>field of size 160-170 bits. Which is considered rock solid like that
>of RSA. Moreover, it parameter and key generation is very fast (upto
>80 times faster then RSA's, if you really believe that in practice RSA
>key gen is a 4th power function of key length). Finally, XTR has a
>curious intrinsic resistance against Differential Power Attacks.
>
>See www.ecstr.com for a detailed description.
So I read the XTR paper (to appear in Crypto) this weekend (a little
airplane reading), and then explained it to a friend who had never studied
extension fields (so now I think I really understand it (and also found
some typos)).
I dispute that the paper demonstrates that XTR resists DPA. (Which is
not to say that it doesn't, just that the claim that it does that's made
in the paper is fallacious.)
> Remark 2.3.9 The only difference between the two different cases in
> Algorithm 2.3.7 (i.e., if the bit is off or on) is the application of
> Corollary 2.3.5.iii if the bit is off and of Corollary 2.3.5.iv if the
> bit is on. The two computations involved, however, are very similar
> and take the same number of instructions. Thus, the instructions
> carried out in Algorithm 2.3.7 for the two different cases are very
> much alike. This is a rather unusual property for an exponentiation
> routine and makes Algorithm 2.3.7 much less susceptible than usual
> exponentiation routines to environmental attacks such as timing
> attacks and Differential Power Analysis.
This seems to me to be the same (incorrect) argument that "shows" that
the following modexp routine is immune to timing and power attacks:
modexp(x, a, p) {
if (a == 0) return 1;
y = modexp(x, int(a/2), p);
y = y*y mod p;
z = y*x mod p;
return (a mod 2 == 1) ? z : y;
}
Each iteration of this routine would perform the same amount of computation
whether the low bit of a was 0 or 1. Yet the above *is* susceptible to
timing and power attacks. I'm fairly confident that sci.crypt archives
will have detailed explanations as to why.
That nit aside (as well as the other nit(*)), I quite enjoyed the paper.
(*) <rant>We're just getting *out* of the RSA patent; now you're proposing
a new cryptosystem with its own, brand-new, 20-year patent? Ugh.</rant>
- Ian
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Comments requested: One way function blast()
Date: 30 May 2000 12:09:12 -0700
zapzing <[EMAIL PROTECTED]> writes:
[snip]
> For all possible 4-bit initialization vectors:
> do this:
> {
> For(i=0; i<Number of 2-bit message blocks;i++)
> {
> Seach for the 2-bits that will give the
> correct hash value for the message block M_i.
> You now have the message block M-i.
> }
> }
>
> Now just choose the message from among the 256
> messages you have that seems to make sense.
> You now also have the initialization vector.
I've reread this a couple times, and I just don't follow. I'm
particularly confused by the "4 bit initialization vector" part.
There is a 2 bit initialization vector, which rotates through the 4
possible values, but it is on a set schedule and not secret at all.
Searching for the proper 2 bits to go back one step was a possibility
I considered. But there are 32 steps. Every time you have more than
one value that works, you have more than one path backwards to try.
With 32 possible forks, each fork having from 0 to 4 possible paths to
proceed along, and an average of 2 paths to try at each fork (that is,
(0+1+2+3+4)/5 = 10/5 = 2), I would expect this not to be any easier
than brute force. Is there a flaw in my reasoning?
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: 30 May 2000 12:19:08 -0700
"Fergus O'Rourke" <[EMAIL PROTECTED]> writes:
> Andru Luvisi <[EMAIL PROTECTED]> wrote in message >
> > This is not a usenet post. This is a binding contract which you have
> > already signed, stating that you must pay me US$1,000,000 on or before
> > July 1st 2000.
>
> Eh?
As someone else already said, a law doesn't avoid being a human rights
violation simply by saying that it isn't, or even by getting a
government person to say that it isn't. Spam is still spam, even if
it starts with "THIS IS NOT SPAM!!!"
The idea is, my post *was* a usenet post, it was *not* a contract, and
nobody signed it. My saying otherwise doesn't make a bit of
difference. Similarly, requiring people to prove they are innocent or
be assumed guilty is a human rights violation. Locking people up for
forgetting a passphrase is a human rights violation. Having a section
in the law which says "this is not a human rights violation" doesn't
change that. Having someone in the government say "this is not a
human rights violation" doesn't change that. It is still a human
rights violation.
Is my point more clear now?
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Tue, 30 May 2000 21:44:34 +0200
tomstd wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >> tomstd <[EMAIL PROTECTED]> wrote
> >> > If I get the 3-pass protocal it is:
> >> >
> >> > A wants to send B 'm'.
> >> >
> >> > 1. A sends m^e mod p
> >> > 2. B sends m^e^d mod p
> >> > 3. A sends m^e^d^-e nod p
> >> >
> >> > B recovers 'm' via m^e^d^-d^-e mod p
> >> >
> >> > Then 'e' and 'd' are your keys. This is hardly 'no-key'
> >> > encryption.
> >> >
> >>
> >> It is no-key in thye sense that neither user has a key.
> >> It's generated on the fly (e.g. a session key) and exchanged
> >> like in Diffie-Hellman.
> >
> >Still, these stuffs generated on the fly are 'fundamentally'
> inaccessible
> >to the analyst and hence are equivalent to (secret) keys. The
> same
> >doesn't seem to apply to using foreign languages.
>
> That's not true, I have m^e, m^de and m^d, from which I could
> plausibly solve if I knew 'm'. There is probably some math
[snip]
Right, that's the unknown (secret, 'key') that you have to figure out.
In bruteforcing a block cipher, the 'key' is also something you
potentially can find out but have to do some work to get (plausibly
solve). So there are in the above case matters that are 'equivalent'
to 'keys'. On the other hand in the case of using foreign languages
everything is entirely open. If an English message in plaintext is
translated into French, it remains a plaintext, isn't it? Or would you
ever call it a ciphertext? (If the opponent did poorly in his French
class in school and consequently can't read the message, we simply
can't help him!)
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: driving me and friends nuts
Date: Tue, 30 May 2000 18:55:31 GMT
Yanko Leskovar wrote:
> MLWMZYZ VSG MLRHHRN WMZ MIFGVI LG VHZY
It is nonstandard, but if you follow the rule "try the simplest
things first", you could stumble upon the answer. In particular,
deciphering it with a reversed standard alphabet (A<->Z, B<->Y,
etc.) helps immensely.
Or, you should have looked at the frequency histogram and asked
whether it matches the standard alphabet or reversed standard
alphabet, which would lead you to perform the same substitution.
The final step then becomes apparent.
------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Crossposted-To: alt.security,comp.security
Subject: Destroy Al Gore's Presidential Election Campaign ....
Date: Tue, 30 May 2000 19:36:06 GMT
Al Gore and his governmental program was involved influencing my
personal life without me having any connections to any governments and
me just being a private person. It appears that my ex-spouse indeed
wanted to attend one of his governmentally run training programs. It is
amazing that people who have paid taxes and have never done anything
wrong have been violated by Al Gore's governmental programs and other
publicly funded influence networks. Makes you stop paying any taxes.
And they still get their pay checks from the U.S. government. Destroy
Al Gore's Presidential election campaign !
Yours,
Markku
Somewhere from Miami, Dade's Library .... read alt.politics.org.cia ...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Eric Verheul" <[EMAIL PROTECTED]>
Subject: Re: any public-key algorithm
Date: Tue, 30 May 2000 21:48:44 +0200
> XTR looks interesting, and I even posted your URL on sci.crypt
> previously, but ...
>
> 1. it hasn't had significant public scrutiny yet.
The DL problem in finite extension fields has been studied exensively
by experts. Just look at the references in our paper.
It hasn't gained much attention though in the popular press, though.
Maybe due to the fact that extension fields are difficult to understand.
Also remember that GF(2^1024) was (is?) used quite extensively and studied!
The attacks for those finite fields (Coppersmith), are just a special
variant of the NFS
These don't work for large p. If there was a cheaper way to break the DL
problem in
general GF(p^6), then this would be probably also applicable to
GF(((2^6)^6)^ etc). No proof,
but a good indication that DL in GF(p^6)* and GF(P)* are indeed comparable
difficult,
when of the same size.
> 2. its only advantage over DL in GF(p) is shorter public keys.
Have you read the paper? Just have a look at the website then,
there you can find the advantages, XTR is much faster than DL in GF(p) and
so
is it's key gen.
> 3. you have patented it, so no one else can use it.
We do give licences though.
regards, Eric
------------------------------
From: "Eric Verheul" <[EMAIL PROTECTED]>
Subject: Re: XTR (was: any public-key algorithm)
Date: Tue, 30 May 2000 21:54:37 +0200
> I dispute that the paper demonstrates that XTR resists DPA. (Which is
> not to say that it doesn't, just that the claim that it does that's made
> in the paper is fallacious.)
>
> > Remark 2.3.9 The only difference between the two different cases in
> > Algorithm 2.3.7 (i.e., if the bit is off or on) is the application of
> > Corollary 2.3.5.iii if the bit is off and of Corollary 2.3.5.iv if the
> > bit is on. The two computations involved, however, are very similar
> > and take the same number of instructions. Thus, the instructions
> > carried out in Algorithm 2.3.7 for the two different cases are very
> > much alike. This is a rather unusual property for an exponentiation
> > routine and makes Algorithm 2.3.7 much less susceptible than usual
> > exponentiation routines to environmental attacks such as timing
> > attacks and Differential Power Analysis.
>
> This seems to me to be the same (incorrect) argument that "shows" that
> the following modexp routine is immune to timing and power attacks:
>
> modexp(x, a, p) {
> if (a == 0) return 1;
> y = modexp(x, int(a/2), p);
> y = y*y mod p;
> z = y*x mod p;
> return (a mod 2 == 1) ? z : y;
> }
>
> Each iteration of this routine would perform the same amount of
computation
> whether the low bit of a was 0 or 1. Yet the above *is* susceptible to
> timing and power attacks. I'm fairly confident that sci.crypt archives
> will have detailed explanations as to why.
We didn't state that is was immune to DPA's, only that we found that
XTR's natural exponentiation routine made it *less* susceptible than usual
exponentiation
routines to environmental attacks such as timing
attacks and Differential Power Analysis.
But please prove us wrong there!
Eric
------------------------------
From: Andy Dingley <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Tue, 30 May 2000 21:15:56 +0100
[EMAIL PROTECTED] (David Boothroyd) a �crit :
>The answer is simple: Don't break the law.
I'm part of a high-budget eCommerce development. Part of our
(perfectly legit) business model involves a use of crypto that could
technically be in breach of RIP. The obvious solution is simply to
host overseas.
Can someone please tell me _anything_ that the Labour Party is doing
to encourage the development of eCommerce in the UK ? Their rhetoric
is fine, their practice is driving the industry out of the country.
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: XTR (was: any public-key algorithm)
Date: 30 May 2000 20:23:37 GMT
In article <8h16vb$9q1$[EMAIL PROTECTED]>,
Eric Verheul <[EMAIL PROTECTED]> wrote:
>> I dispute that the paper demonstrates that XTR resists DPA. (Which is
>> not to say that it doesn't, just that the claim that it does that's made
>> in the paper is fallacious.)
>>
>> > Remark 2.3.9 The only difference between the two different cases in
>> > Algorithm 2.3.7 (i.e., if the bit is off or on) is the application of
>> > Corollary 2.3.5.iii if the bit is off and of Corollary 2.3.5.iv if the
>> > bit is on. The two computations involved, however, are very similar
>> > and take the same number of instructions. Thus, the instructions
>> > carried out in Algorithm 2.3.7 for the two different cases are very
>> > much alike. This is a rather unusual property for an exponentiation
>> > routine and makes Algorithm 2.3.7 much less susceptible than usual
>> > exponentiation routines to environmental attacks such as timing
>> > attacks and Differential Power Analysis.
>>
>> This seems to me to be the same (incorrect) argument that "shows" that
>> the following modexp routine is immune to timing and power attacks:
>>
>> modexp(x, a, p) {
>> if (a == 0) return 1;
>> y = modexp(x, int(a/2), p);
>> y = y*y mod p;
>> z = y*x mod p;
>> return (a mod 2 == 1) ? z : y;
>> }
>>
>> Each iteration of this routine would perform the same amount of
>> computation whether the low bit of a was 0 or 1. Yet the above *is*
>> susceptible to timing and power attacks. I'm fairly confident that
>> sci.crypt archives will have detailed explanations as to why.
>
>We didn't state that is was immune to DPA's, only that we found that
>XTR's natural exponentiation routine made it *less* susceptible than
>usual exponentiation routines to environmental attacks such as timing
>attacks and Differential Power Analysis. But please prove us wrong
>there!
I just don't see any reason why XTR is less susceptible to environmental
attacks than the above modexp code.
[Do you have a general statement as to licensing terms, or will you be
playing the (original) RSA game of "talk to each potential user"?]
- Ian (I really enjoyed the "pth powers are free" trick...)
------------------------------
Subject: Does it even matter?
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 30 May 2000 13:28:31 -0700
As some of you may already know, I was offered a job with RSA
this summer (in San Mateo) working on some software. Sounds
great seems like people appreciate my work, obviously since I am
not even done high school.
Of course they hype me up about the job, get me all excited.
And what happends (thru no fault of RSA) big old mr government
steps in and acts like a dolt. I can't get the job because I
don't have a "post-secondary education diploma with three years
work experience". Super, if I had a job, why would I move 3000
miles to work in the states?
Anyways, I am beginning to think my research is pointless since
well I would rather focus on my school now and prepare for the
exciting job as a mop-jocky.
It has been nice chatting with you guys, maybe I will come back
some time.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Crossposted-To: alt.security,comp.security
Subject: Re: Destroy Al Gore's Presidential Election Campaign ....
Date: Tue, 30 May 2000 13:37:46 -0700
"Markku J. Saarelainen" wrote:
> Al Gore and ... my ex-spouse ...
> amazing that people who have paid taxes ...
I suggest you find an appropriate forum for your complaints.
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Does it even matter?
Date: 30 May 2000 13:47:54 -0700
We'll miss you.
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
Date: Tue, 30 May 2000 16:06:21 -0400
rick2 wrote:
>
> I would like to use some strong encryption but need to have
> the output not have any zeros (needs to fit into zero-terminated
> data chunks). What would be the smallest and fastest way to mask
> the zeros? I've seen some people expand every 7 bits to 8, but
> that seems wasteful (expands to 114% of original size, or so) and
> takes time (every output byte needs to be shifted).
That's an ancient problem, solved in a number of different
ways in various communications links.
1. The Bisync solution: pick some byte (for your application
any non-zero value will do since you're dealing with encrypted
data) to be the "escape". Say it's 0x01. Then replace each
occurrence of 0x01 in the original data with 0x01 0x01, and
each occurrence of 0x00 with 0x01 0x02.
2. The HDLC solution: consider the message as a bitstring (rather
than a byte string). Each time you see 6 zero bits in a row, insert
a one bit. (Actually, for your purposes it could be when you see
7 zero bits in a row, but 6 is the classic HDLC rule.)
I'd assume (1) is easier to do in software. It is also more efficient;
the overhead is 0.78% vs. 1.56% for (2), given uniform distribution of
input data patterns as should be the case here.
paul
------------------------------
** 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
******************************
