Cryptography-Digest Digest #538, Volume #11 Wed, 12 Apr 00 21:13:01 EDT
Contents:
Re: Stream Cipher - Mark 2. (Tom St Denis)
Re: Stream Cipher - Mark 2. (Tom St Denis)
SSL/HTTP questions (newbie warning) (Ken Tomei)
Re: Compaq invents more efficient RSA?! (Jerry Coffin)
Re: Compaq invents more efficient RSA?! (Jerry Coffin)
Re: SSL/HTTP questions (newbie warning) (Paul Rubin)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (lordcow77)
Re: Encode Book? (Tom St Denis)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (Tom St Denis)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (Tom St Denis)
Re: Compaq invents more efficient RSA?! (Doug Stell)
Re: Compaq invents more efficient RSA?! (Roger)
Re: GSM A5/1 Encryption (Paul Schlyter)
Re: Encode Book? (David A Molnar)
Re: Compaq invents more efficient RSA?! (Bodo Moeller)
Re: Geneneral Criptanalysis Information (Scott Contini)
Re: RC6 world fastest realization - true or fake (Scott Contini)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Stream Cipher - Mark 2.
Date: Wed, 12 Apr 2000 22:25:25 GMT
Simon Johnson wrote:
>
> My last attempt at generating stream characters was pretty poor.... ( and a
> total clone) I hope this algorithm is a little more robust, altough this
> is probably not the case. :). This stream-generator seems to produce a
> random looking stream. Altough i havn't analyised it in any shape or form.
>
> The following function produces one stream character:
>
> Function StreamCharacter {
> For i = 1 to (length of key)
> a = (a + (a * b * (ascii of the i'th character of key))) mod 65536
> b = (b + (a * b * (ascii of the (i+1)'th character of key))) mod 65536
> Next i
> outputchar = (a+b) mod 256
> }
>
> N.B. the (i+1)'th character is calculated by 'a=(i+1) mod len(key): if a=0
> then a= len(key)'
Also if 'b=0' then you get 'a += char[i]', which is a bad idea. Also
you have to realize you are cloning a fibonacci sequence with the use of
multiplication intersped. Also that the period of this RNG is most
likely vary short, at most 2^32 bytes, also that the upper 8 bits of (a,
b) play no role whatsoever in the output, so you can simply truncate (a,
b) modulo 256 in the inner loop.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Stream Cipher - Mark 2.
Date: Wed, 12 Apr 2000 22:26:32 GMT
Tom St Denis wrote:
>
> Simon Johnson wrote:
> >
> > My last attempt at generating stream characters was pretty poor.... ( and a
> > total clone) I hope this algorithm is a little more robust, altough this
> > is probably not the case. :). This stream-generator seems to produce a
> > random looking stream. Altough i havn't analyised it in any shape or form.
> >
> > The following function produces one stream character:
> >
> > Function StreamCharacter {
> > For i = 1 to (length of key)
> > a = (a + (a * b * (ascii of the i'th character of key))) mod 65536
> > b = (b + (a * b * (ascii of the (i+1)'th character of key))) mod 65536
> > Next i
> > outputchar = (a+b) mod 256
> > }
> >
> > N.B. the (i+1)'th character is calculated by 'a=(i+1) mod len(key): if a=0
> > then a= len(key)'
>
> Also if 'b=0' then you get 'a += char[i]', which is a bad idea. Also
> you have to realize you are cloning a fibonacci sequence with the use of
> multiplication intersped. Also that the period of this RNG is most
> likely vary short, at most 2^32 bytes, also that the upper 8 bits of (a,
> b) play no role whatsoever in the output, so you can simply truncate (a,
> b) modulo 256 in the inner loop.
Doh, which would mean the period is at most 2^16 for the output, since
the top bytes don't contribute to the output.
------------------------------
From: Ken Tomei <[EMAIL PROTECTED]>
Subject: SSL/HTTP questions (newbie warning)
Date: Wed, 12 Apr 2000 15:28:22 -0700
Hello,
Hopefully I'm posting these questions to the most appropriate newsgroup,
if not please feel free to directly me elsewhere. I'm trying to get a
clear understanding of SSL protocols, but several important issues are
still unclear to me.
First, my understanding is that initial session establishment requires a
full handshake, including certificate exchange. Each TCP connection
under that session ID is initiated using a simplified handshake, using
the previously calculated master secret, but different client and server
randoms to generate different symmetric keys. Are these client and
server hello messages transmitted in the clear or are they encrypted?
After a session is closed, can it be resumed later?
Also, is it possible to have multiple TCP connections open
simultaneously within the same session or will they always occur
sequentially?
Servers typically have a session timeout counter - what exactly does
this entail? Is this a strict timer from the session establishment, or
is the counter reset with each new TCP connection? In other words, does
the timer only start when a session becomes inactive?
Finally, how does this all relate to a typical SSL session that I'll
encounter over the web? For example, I click on BofA.com and establish
a secure session. Are multiple TCP connections opened for each imbedded
object on that particular page? After I've retreived all objects on
that page, is the session closed or still active? When I click on a new
link within the secure site, do a resume the same session? open a new
one?
How do persistant connections affect all of this?
I'm having trouble locating a good reference to understand a general
SSL model. Any help would be greatly appreciated.
Thanks,
Ken
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Compaq invents more efficient RSA?!
Date: Wed, 12 Apr 2000 17:00:31 -0600
In article <[EMAIL PROTECTED]>, the_nsa@my-
deja.com says...
[ ... ]
> Supposedly, inspired by the necessity of having secure protocols
> for nukes, the NSA invented the idea of public key crypto in the
> 1960s. (This was before the Brits at Cheltenham who were before
> DH & RSA.) I'd bet money the NSA has previously considered RSA
> with more than 2 prime factors. I wonder what their internal
> policy is for allowing themself to apply for patents.
With changes in patent policy, they've probably changed this, but at
the time I believe their policy was as follows:
They'd apply for the patent when they invented something. Then,
they'd tell the patent office that the application was classified.
Since the patent MUST be disclosed when it's granted, this kept the
patent from actually being granted. Then, when/if the information
became publicly known, the NSA would allow the patent to be granted,
so whoever re-invented it STILL couldn't use it -- the NSA still had
exclusive rights to the invention for the next 17 years.
Now the patent policy has changed though: instead of expiring 17
years after being granted, a patent expires 20 years after
application. OTOH, the US patent system is based on who was the
first to invent something, not who was first to file the patent
application -- that means the NSA could simply keep the invention
secret, and when/if somebody else applies for a patent, they apply
for a patent based on their earlier invention, so the new one gets
rejected.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Compaq invents more efficient RSA?!
Date: Wed, 12 Apr 2000 17:00:29 -0600
In article <[EMAIL PROTECTED]>, djohn37050
@aol.com says...
> It would be interesting to see exactly the claims of the Compaq patent.
Doing some searching, it looks like it's patent number 5,848,159.
Based on the disclosure, it appears to me that what the inventors
thought was original was NOT simply the user of three or more factors
in the modulus. Instead, they think they invented a method of
carrying out decryption in parallel on a number of processors by
using the chinese remainder theorem recursively.
I'm not at all sure the claims accurately reflect that though: it
looks to me like claim 1 attempts to cover all possible use of RSA
where the modulus has more than 2 factors and claim 2 covers all
decryption of messages encrypted according to claim 1. I haven't
examined all the claims in detail, but didn't notice any that
appeared to mention the original intent that the preferred embodiment
use parallel processing to improve speed.
The patent might remain valid (though quite narrow) due to one fact:
some of the elements of some claims are given as "means for...",
which may or may not be interpreted by a court as indicating that
these are means claims. If they are, then an infringing means must
be either the same as, or equivalent to, a means given in the
disclosure of the patent -- this might be enough for the original
intent of parallel processing to be considered (in essence) part of
what's claimed, which could thereby render the claim truly new,
unique, novel, etc., and thereby make the claim valid.
OTOH, I'm not a lawyer, and in situations like this, even judges on
the Court of Appeals for the Federal Circuit end up disagreeing about
whether a particular claim is really a means claim or not, so my word
is only that of an interested observer; it shouldn't be considered
the final word, and _certainly_ shouldn't be taken as legal advice.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: SSL/HTTP questions (newbie warning)
Date: 12 Apr 2000 23:05:24 GMT
In article <[EMAIL PROTECTED]>, Ken Tomei <[EMAIL PROTECTED]> wrote:
>First, my understanding is that initial session establishment requires a
>full handshake, including certificate exchange. Each TCP connection
>under that session ID is initiated using a simplified handshake, using
>the previously calculated master secret, but different client and server
>randoms to generate different symmetric keys. Are these client and
>server hello messages transmitted in the clear or are they encrypted?
The hello messages are in the clear.
>After a session is closed, can it be resumed later?
This is spelled out in the spec. I'm pretty sure the answer is no
but I'd have to check.
>Also, is it possible to have multiple TCP connections open
>simultaneously within the same session or will they always occur
>sequentially?
SSL operates at a higher level than TCP. However, in most implementations,
you won't have several TCP connections being multiplexed into a single
SSL connection.
>Servers typically have a session timeout counter - what exactly does
>this entail? Is this a strict timer from the session establishment, or
>is the counter reset with each new TCP connection? In other words, does
>the timer only start when a session becomes inactive?
It's just something that the server does at its convenience to know when
to expire entries in its ssl session cache.
>encounter over the web? For example, I click on BofA.com and establish
>a secure session. Are multiple TCP connections opened for each imbedded
>object on that particular page? After I've retreived all objects on
>that page, is the session closed or still active? When I click on a new
>link within the secure site, do a resume the same session? open a new
>one?
I think you'd open new SSL sessions but can use cached keys. It's
been a while since I've looked at this.
>How do persistant connections affect all of this?
If you mean HTTP 1.1 keepalive connections, that's independent.
>I'm having trouble locating a good reference to understand a general
>SSL model. Any help would be greatly appreciated.
Try RFC 2246, the TLS specification. http://www.faqs.org/rfcs/rfc2246.html.
------------------------------
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
From: lordcow77 <[EMAIL PROTECTED]>
Date: Wed, 12 Apr 2000 16:14:28 -0700
In article <[EMAIL PROTECTED]>, DMc
<[EMAIL PROTECTED]> wrote:
>2 147 466 840 = ((16 807^1 073 741 824) * 1) mod 2 147 483 647
>was already given in "context." What was asked of you was the
>easy, and now "trivial," calculation which makes this true. So
far,
You can do the modular reduction after every multiplication, if
you want to do the calculation the naive way. Alternatively, you
can do everything in 31 modular squarings and reductions via the
classical square and multiply method. Montgomery representations
are also a viable option, but aren't worth the trouble in this
case. More detailed descriptions can be found in any decent
algorithms book; certainly, _Seminumerical Algorithms_ has a
very complete explanation of these and more sophistocated
methods (such as addition chain generation and windowed
exponentiation).
* 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: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Encode Book?
Date: Wed, 12 Apr 2000 23:25:47 GMT
James Felling wrote:
>
> I learned pascal at about the same age. It was a big achievement, but
> not on the same order as Ms. Flannery's achievement. You are gifted and
> talented, but she has done something that was truly extraordinary. Live
> with it.
Not to be a jealous type, but how much of it was here idea, and not her
fathers coaxing? hehehe, just kiddin I actually don't know much at all
about her so that's no a fair comment, sorry... but makes you wonder :)
Anyways, does she have a website of her own? If so where is it?
And I don't view learning a programming language by ourselve as an
everyday activity for twelve year olds. Or writting your own Bulletin
Board System (BBS) when you are 13, or etc... Anyways, nuff ranting I
bet we are all just gifted in our own domains. She is probably wicked
at math, but couldn't play the piano etc... So no reason to be bitter,
right?
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: Wed, 12 Apr 2000 23:27:23 GMT
[EMAIL PROTECTED] wrote:
>
> In article <[EMAIL PROTECTED]>, Tom St Denis <[EMAIL PROTECTED]> writes:
> > But if you sum three single digit numbers they will be on avg [the
> > output] near 4.5. So that can't be entirely random.
>
> Do you mind sharpening this point for us?
>
> What is it about the distribution the sum of three random single digit
> numbers that is non-random? As opposed to non-uniform. And what does
> this distribution have to do with the distribution of the sum of 1 times
> the first plus 10 times the second plus 100 times the third?
>
> Or is your sarcasm simply too subtle for me?
I missed the fact that he was adding in diff mag of digits. So it's
actually D1 + 10*D2 + 100*D3, in which case he isn't adding the digits
at all [to each other] they are just different components of the number.
If for example he *were* doing R = D1+D2+D3 / 3, that would be entirely
non random.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: Wed, 12 Apr 2000 23:29:30 GMT
What is the big deal about this? MuPad found the solution [same as
yours] in under a second....
Tom
lordcow77 wrote:
>
> In article <[EMAIL PROTECTED]>, DMc
> <[EMAIL PROTECTED]> wrote:
> >2 147 466 840 = ((16 807^1 073 741 824) * 1) mod 2 147 483 647
> >was already given in "context." What was asked of you was the
> >easy, and now "trivial," calculation which makes this true. So
> far,
>
> You can do the modular reduction after every multiplication, if
> you want to do the calculation the naive way. Alternatively, you
> can do everything in 31 modular squarings and reductions via the
> classical square and multiply method. Montgomery representations
> are also a viable option, but aren't worth the trouble in this
> case. More detailed descriptions can be found in any decent
> algorithms book; certainly, _Seminumerical Algorithms_ has a
> very complete explanation of these and more sophistocated
> methods (such as addition chain generation and windowed
> exponentiation).
>
> * 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: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: Compaq invents more efficient RSA?!
Date: Wed, 12 Apr 2000 23:11:51 GMT
>Supposedly, inspired by the necessity of having secure protocols
>for nukes, the NSA invented the idea of public key crypto in the
>1960s. (This was before the Brits at Cheltenham who were before
>DH & RSA.)
Do you have any pointers to this early work?
I've seen the declassified directive from Pres. Kennedy requesting
development of this for controlling nukes and I've read the accounts
of Clifford Cocks, but this is new.
>I wonder what their internal
>policy is for allowing themself to apply for patents.
DSA was created by the NSA and patented and it was in everyone's
interest to get that algorithm out into the public. I am told that it
depends on whether or not they want to reveal the details to the
public or want to hide the fact that something even exists. I've also
been told that they had the opportunity to challenge the D-H and RSA
patents, but chose to not reveal that they already had these
algorithms. Industry and the patent system works toward financial
gain, while the NSA is concerned about the national security.
Decisions are generally made on that basis.
>I toy with Big Brother, yet He does not share His toys with me :-(
>* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
>The fastest and easiest way to search and participate in Usenet - Free!
We have seen a few cases whey they have shared, e.g., recent work on
ECC standards. They have also stated that they are beginning to rely
on the accademic community to help develp algorityms. I wouldn't
surprised is they use an AES algorithm or some derivative thereof in
the near future.
------------------------------
From: Roger <[EMAIL PROTECTED]>
Subject: Re: Compaq invents more efficient RSA?!
Date: Wed, 12 Apr 2000 17:11:20 -0700
Jerry Coffin wrote:
> Doing some searching, it looks like it's patent number 5,848,159.
>
> Based on the disclosure, it appears to me that what the inventors
> thought was original was NOT simply the user of three or more factors
> in the modulus. Instead, they think they invented a method of
> carrying out decryption in parallel on a number of processors by
> using the chinese remainder theorem recursively.
The inventors would have had to swear that claims 1 & 2 were
original to them.
> I'm not at all sure the claims accurately reflect that though: it
> looks to me like claim 1 attempts to cover all possible use of RSA
> where the modulus has more than 2 factors and claim 2 covers all
> decryption of messages encrypted according to claim 1. I haven't
> examined all the claims in detail, but didn't notice any that
> appeared to mention the original intent that the preferred embodiment
> use parallel processing to improve speed.
These claims are clearly invalid. I don't have the papers handy,
but I am sure that Rivest et al explicitly described the
possibility of using multiple primes about 20 years ago.
"A key assumption of the present invention is that n, composed of 3 or
more sufficiently large distinct prime numbers, is no easier
(or not very much easier) to factor than the prior art, two prime number
n."
Experts in the field have thought this for about 10 years,
and used it as a reason to use 3-factor RSA.
"The present invention is capable of using the RSA scheme to perform
encryption and decryption operation using a large (many
digit) n much faster than heretofore possible."
Not true.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: GSM A5/1 Encryption
Date: 13 Apr 2000 00:09:57 +0200
In article <8d2ho9$7hl$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> Paul Koning <[EMAIL PROTECTED]> wrote:
>
>> Well, you cannot possibly have a valid argument that (a) they
>> knew exactly what they were doing and also (b) they were surely
>> no students of crypto. Apart from that, the fact that they
>> ignored the established ciphers, designed a cipher substantially
>> weaker than even the absurdly weak goals they set, and the fact
>> that they kept it secret rather than releasing it to public
>> scrutiny all support my comment.
>>
>> Re David Wagner's comments, you mean comments like:
>> "In the world of crypto, there are plenty of "tried and true"
>> strong ciphers (strong enough for the context of GSM that
>> there was no need to go with an "on the edge" cipher like
>> 64- or 54-bit A5/1)."
>> ?
>
> No the reference here is to the fact that the designers...were not
> amateurs...this design was to produce a deliberate week cipher...see the
> messages in this thread...mine and David Wagner's..you can also read
> about it in Applied Crypto
If they wanted a weak cipher, why didn't they use a simple Caesar
cipher, or no encryption at all?
BTW, the argument that the encryption deliberately was made weak to
enable e.g. the police to eavesdrop is pretty lame: the police could
instead intercept the call between the base stations, where the phone
call passes unencrypted. Then they won't have to bother at all with
cracking even a weak encryption.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Encode Book?
Date: 13 Apr 2000 00:04:26 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Not to be a jealous type, but how much of it was here idea, and not her
> fathers coaxing? hehehe, just kiddin I actually don't know much at all
> about her so that's no a fair comment, sorry... but makes you wonder :)
Some months ago on Coderpunks, Dr. Purser posted on this specific
question "How much was her idea, and how much came from others?"
>From what I understand, he was her supervisor during an internship
at Baltimore Technologies (an Irish cryptography firm). His claim
was that he had suggested that she look at matrix-type cryptosystems,
and that she developed the entire algorithm from there.
Details can probably be found by searching for his message. Anyway, I
have no reason to doubt his claim.
> Anyways, does she have a website of her own? If so where is it?
I don't know if she has a website. Why is it relevant? Are you
suggesting that a web site is necessary to be a cryptographer?
I don't think Tatsuaki Okamoto has a web site either. If you don't know
who he is, do a web search...
Thanks,
-David
------------------------------
From: [EMAIL PROTECTED] (Bodo Moeller)
Subject: Re: Compaq invents more efficient RSA?!
Date: 13 Apr 2000 00:13:56 GMT
Bodo Moeller <[EMAIL PROTECTED]>:
[...]
> The idea of using an RSA modulus with more than two prime factors has
> already been patented, and in fact the patent expires in a few months.
> See <URL: http://www.patents.ibm.com/details?&pn=US04405829__&s_clms=1#clms>,
> claim 38 (also at <URL:
>http://www.patents.ibm.com/gifcache/US04405829__.tif.19.s0.35.r0.gif>).
For those who don't have web access, or are too lazy to look this up:
it's the original RSA patent. Most claims are about the usual
p*q variant, but some claims describe the general case.
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Geneneral Criptanalysis Information
Date: 13 Apr 2000 00:53:56 GMT
In article <8d1ufo$g4o$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Hi,
>
> I'd like to learn something about ciptanalysys, but I can't find
>information about the methods that are used. I've read a lot about
>criptography, and I wish to expand my knowledge.
> Can anyone recomend me some information source??
>
>Thanks in advance
>
>
> WSM
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
About a week ago, Alex Birukov posted about a cryptanalysis course that
he will be teaching over the web. See:
http://www.wisdom.weizmann.ac.il/home/albi/public_html/cryptanalysis/
Looks like a great course. I wish I had time to participate in it.
Scott
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: RC6 world fastest realization - true or fake
Date: 13 Apr 2000 01:00:11 GMT
In article <[EMAIL PROTECTED]>,
Ilya Levin <[EMAIL PROTECTED]> wrote:
>Here is a RC6 implementation source code. The person, provided
>it, claim this is his personal and unique code has been awarded
>and recognized as a RC6 world fastest realization. Can somebody
>comment it, please?
>
>Sincerely,
>Ilya O. Levin
>Nattyware Research Lab
>http://natty.port5.com
>
I don't have access to a Pentium to try the code out, but the fastest
Pentium Pro RC6 implementation that I'm aware of is 223 cycles by
Aoki and Lipmaa.
see:
http://home.cyber.ee/helger/aes/table.html
They have also written a paper on their AES implementations, which is
available at:
http://home.cyber.ee/helger/papers/al00/
Scott
------------------------------
** 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
******************************
