Cryptography-Digest Digest #136, Volume #11 Wed, 16 Feb 00 19:13:01 EST
Contents:
Re: EOF in cipher??? (Mok-Kong Shen)
Re: Q: Division in GF(2^n) (Mok-Kong Shen)
Re: Q: Division in GF(2^n) (Mok-Kong Shen)
Re: multi-precision integer C library ("Dann Corbit")
US National Security, Economic Intelligence and Encryption ("William A. Nelson")
Re: My background - Markku Juhani Saarelainen ("William A. Nelson")
Re: RSA Speed (Doug Stell)
Re: Does RSA use real prime ? (lordcow77)
Re: Block chaining (Adam Back)
Re: source code export laws (wtshaw)
Re: RSA Speed (Paul Rubin)
Re: OAP-L3 Encryption Software - Complete Help Files at web site ("Joseph Ashwood")
code still unbroken ("Chuck Davis")
Re: Does the NSA have ALL Possible PGP keys? ("Douglas A. Gwyn")
Re: Question about OTPs ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Wed, 16 Feb 2000 23:27:31 +0100
Stephen Houchen wrote:
>
> If you're programming in C, open the file as "binary" (mode "rb", for
> example).
I am ignorant of what the C standard specifies. Question: Does
'binary' require the file to be multiple of words or just any multiple
of bytes will do? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Division in GF(2^n)
Date: Wed, 16 Feb 2000 23:28:08 +0100
Paul Koning schrieb:
>
> Well, certainly patenting mathematics is as absurd as patenting
> genetics, but both seem to be permitted by the US patent office
> these days. Whether that's because of some random decisions they
> made or because of real legal authority is entirely unclear to me.
>
> But you don't need to worry about most of the cases you mentioned.
> School math is clearly not patentable -- it's not "novel". So while
> a patent covering school math would probably be approved given
> how the patent office "operates" these past few years, that patent
> would nevertheless not be valid and would not hold up under
> challenge, which is what matters most.
I am not quite sure of that. I can't see e.g. that using the relation
1/B = B^(2^n-2) is anything that qualify as 'novel' at all. (It is
one of the 'basic' facts that the order of a non-zero element divides
p^m-1 in GF(p^m).) The situation as I perceive is the following:
There has been in the past some number-theoretic operations that
got patented. Because of such 'precedences' the patent office
has difficulties to refuse other number-theoretical stuffs to be
patented also, even these are very trivial. If that practice
continues, one ends up with virtually all the mathematical
computations in practice patented. This is in my humble view a
very serious and critical issue, having, I believe, a very far
reaching impact on the society. (Doesn't everything in the modern
world depend on mathematics?) Sure, patenting genes is bad enough.
But there are at least some loud voices against that, while
patenting mathematics appears to go on very silently without the
public's attention at all.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Division in GF(2^n)
Date: Wed, 16 Feb 2000 23:28:01 +0100
Mike Rosing schrieb:
>
> Mok-Kong Shen wrote:
> > > However, AFAICS it is *much* less efficient (at least for software
> > > implementations with field sizes of interest in cryptography) than
> > > calculating the inverse of B using the Almost Inverse algorithm, and
> > > multiplying A by the inverse.
> >
> > Why is that 'Almost'? Isn't it exact, if one uses B^(-1)=B^(2^n-2)?
>
> That's the name given to an algorithm published by Schroppel a few years
> back.
> You end up with 1/B * u^k, and for some systems inverting u^k is simple.
Computing B^(2^n-2) can be done straightforwardly, essentially
in the way described in the patent text. Does Schroppel's method
work differently? What is u in your last sentence above and what's
the trick of inverting u^k in some systems? Please kindly explain.
Many thanks in advance.
M. K. Shen
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: multi-precision integer C library
Date: Wed, 16 Feb 2000 14:29:38 -0800
"BBC-Igor" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Can anyone point me in the right direction of a well-documented
multi-precision integer arithmetic C library?
Here's MIRACL:
http://indigo.ie/~mscott/
You might also look into Freelip, GMP etc. A web search is better than a
newsgroup query for this sort of thing.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: "William A. Nelson" <[EMAIL PROTECTED]>
Crossposted-To: alt.math
Subject: US National Security, Economic Intelligence and Encryption
Date: Wed, 16 Feb 2000 22:26:38 GMT
US National Security, Economic Intelligence and Encryption
Many ordinary individuals do not understand and realize that the
National Security Strategy of the USA is based very heavily on the
economic security and the implementation of the intelligence strategy in
which a key element of the whole global intelligence cycle is electronic
business intelligence. There are companies that are focussing purely on
the collection and analysis of electronic business intelligence (all
forms of the intelligence). There are systems in place to be implemented
in the future in many regions of the world that have already been
implemented in the USA. These are elements of the USA's strategic
intelligence initiatives. Often also called the system of systems -
actually I have also the model of intelligence islands to describe their
arrangements. So whatever you know now about the Internet and its
intelligence acquisition methods and techniques, these have been known
for years by specific security and intelligence groups working for
certain multinational corporations before these matters ever became the
public knowledge. Actually, one of my key objectives in 1999 was also to
influence European parliamentary and other members to improve the
information security in Europe and protect European business
intelligence. Since March and April, 1999 I have communicated with many
European governmental people. My email address that was taken to use in
April, 1999 was [EMAIL PROTECTED] that is Markku Saarelainen European
Leadership Institute. Got the picture. The objective is to eliminate the
leadership of the USA's economic and business intelligence collection
and its systems. In August, 1999, I actually learned very good
developments that were initiated by one ex-Finance Minister of Finland
in the European Parliament.
Will you perform complete analysis of my USENET postings since
March-April, 1999 and even before that?
I have used 14 different email addresses in the past five years.
Best wishes,
William
----
Actually, the character of Markku J. Saarelainen in 1999 and 2000 was
the invention of William A. Nelson who used the identity of Markku J.
Saarelainen to try to capture some ex-KGB officers who were specializing
in encryption and cryptography. Actually, William A. Nelson was not able
to capture any using the character, because the project went wrong and
only one Finnish person (not a KGB officer, but some information
security expert) came. He provided some specific information for this
character. So William A. Nelson was just using the identity of Markku J.
Saarelainen. There was never a real person, Markku J. Saarelainen, on
the USENET - he was just designed and modeled after a real
experimentation and was doing what William A. Nelson wanted this
character to do on the Internet. Actually, the project lasted for some
time in 1999 and 2000.
I wish that this helped you.
Greetings,
William A. Nelson
=====
------------------------------
From: "William A. Nelson" <[EMAIL PROTECTED]>
Subject: Re: My background - Markku Juhani Saarelainen
Date: Wed, 16 Feb 2000 22:45:49 GMT
=====
I, William A. Nelson, indeed stole the identity of Markku J. Saarelainen and
proceeded to analyze various aspects of encryption and cryptography. I have
been focusing on some high level policy analysis and detailed methods and
technologies. Basically, I, William A. Nelson, stole business files and secrets
of Markku J. Saarelainen. Here is some encryption relevant information from
1996, 1997 and so (published by USIA or other US governmental organization). I,
William A. Nelson, have been following the encryption debate since the early
1990's and have made significant efforts to lower barriers for encryption
exports.
http://home.earthlink.net/~mjsion/washington/Washingt.mbx
Greetings,
William A. Nelson
My URL: http://homestead.virtualjerusalem.com/waeg/
======
US National Security, Economic Intelligence and Encryption
Many ordinary individuals do not understand and realize that the National
Security Strategy of the USA is based very heavily on the economic security and
the implementation of the intelligence strategy in which a key element of the
whole global intelligence cycle is electronic business intelligence. There are
companies that are focussing purely on the collection and analysis of
electronic business intelligence (all forms of the intelligence). There are
systems in place to be implemented in the future in many regions of the world
that have already been implemented in the USA. These are elements of the USA's
strategic intelligence initiatives. Often also called the system of systems -
actually I have also the model of intelligence islands to describe their
arrangements. So whatever you know now about the Internet and its intelligence
acquisition methods and techniques, these have been known for years by specific
security and intelligence groups working for certain multinational corporations
before these matters ever became the public knowledge. Actually, one of my key
objectives in 1999 was also to influence European parliamentary and other
members to improve the information security in Europe and protect European
business intelligence. Since March and April, 1999 I have communicated with
many European governmental people. My email address that was taken to use in
April, 1999 was [EMAIL PROTECTED] that is Markku Saarelainen European
Leadership Institute. Got the picture. The objective is to eliminate the
leadership of the USA's economic and business intelligence collection and its
systems. In August, 1999, I actually learned very good developments that were
initiated by one ex-Finance Minister of Finland in the European Parliament.
Will you perform complete analysis of my USENET postings since March-April,
1999 and even before that?
I have used 14 different email addresses in the past five years.
Best wishes,
William
----
Actually, the character of Markku J. Saarelainen in 1999 and 2000 was the
invention of William A. Nelson who used the identity of Markku J. Saarelainen
to try to capture some ex-KGB officers who were specializing in encryption and
cryptography. Actually, William A. Nelson was not able to capture any using the
character, because the project went wrong and only one Finnish person (not a
KGB officer, but some information security expert) came. He provided some
specific information for this character. So William A. Nelson was just using
the identity of Markku J. Saarelainen. There was never a real person, Markku J.
Saarelainen, on the USENET - he was just designed and modeled after a real
experimentation and was doing what William A. Nelson wanted this character to
do on the Internet. Actually, the project lasted for some time in 1999 and
2000.
I wish that this helped you.
Greetings,
William A. Nelson
=====
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: RSA Speed
Date: Wed, 16 Feb 2000 22:40:26 GMT
On Wed, 16 Feb 2000 15:23:45 -0500, Erik <[EMAIL PROTECTED]> wrote:
>I wrote a program to do RSA with a 1100 bit modulus. I use 65537 for
>the public key exponent, and the private key exponent is, of course,
>near 1100 bits. It works, and encrypting with the public key takes
>about a quarter of a second, but decrypting with the private key takes
>43 seconds on a 400 MHz Pentium. Does this seem right?
Sounds about right, w.r.t., the difference in time. The actual time is
a different matter.
As a starting point for simple approaches, the time required should be
about proportional to the sum of the number of bits (number of
squares) plus the number of 1-bits (number of multiplies) in the
exponent. 65537 has a weight of 19, while a 1100 bit private key has a
weight somewhere around 1650, assuming that half the bits are ones.
That's a ratio of 1:86.8, which is near what you are seeing.
Now, you should investigate faster implementations to get both times
down. The HAC will give you lots of good algorithms and existing large
integer libraries will give you good implementation ideas. Mongomery
multiplication is probably your best choice to use in the
exponentiation. Once you get a fast math library in place, C.R.T. will
knock the private key computation down by a factor of about 4.
doug
------------------------------
Subject: Re: Does RSA use real prime ?
From: lordcow77 <[EMAIL PROTECTED]>
Date: Wed, 16 Feb 2000 15:10:29 -0800
In article <[EMAIL PROTECTED]>, Paul Koning
<[EMAIL PROTECTED]> wrote:
>Yes. On the other hand, I believe you can do non-probabilistic
>primality tests too. Those are quite a lot slower but still
>quite fast -- much faster than simplistic approaches like trying
>all possible divisors...
Not true! No composite has been shown to pass a strong pseudo-
primality test to base 2 and a Lucas sequence test. The total
cost is about the same as for 3 to 4 strong pseudo-primality
tests.
* 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: Adam Back <[EMAIL PROTECTED]>
Subject: Re: Block chaining
Date: Wed, 16 Feb 2000 18:15:58 -0500
David Wagner wrote:
> > However... Plaintext Block Chaining (PBC), and Plaintext FeedBack (PFB)
> > modes allow parallel processing in the encryption direction.
>
> Are these ones secure, when used with non-random plaintexts?
> (e.g., English text as the plaintext)
>
> I'm not worried so much about chosen-text attacks as whether there is
> the possibility that they might share some of the weaknesses of ECB mode,
> but to a lesser extent. Any thoughts?
I looked at them and came to that conclusion.
PCB is:
C_i = E_k(P_i xor P_{i-1})
if any pair P_k, P_{k+1} xor to the same value we have the ECB code book
problem.
Similarly PFB is:
C_i = E_k(P_{i-1}) xor P_i
which is possibly worse in that if any pair P_i == P_j, i!=j, we can obtain
the xor of the next two plaintexts:
C_{i+1} = E_k(P_i) xor P_{i+1}
C_{j+1} = E_k(P_j) xor P_{j+1}
if P_i == P_j, then:
C_{i+1} xor C_{j+1} = P_{i+1} xor P_{j+1}
Both seem very dubious.
Adam
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: source code export laws
Date: Wed, 16 Feb 2000 16:20:29 -0600
In article <[EMAIL PROTECTED]>, Paul Koning <[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
> >
> > Let me make a point or two with some code. ROT13 should be tame enough:
>
> You probably should have sent a copy of that to the BXA before you
> posted
> it (if you're in the USA). :-)
>
The point is that the only difference between a crypto program and one
that is not is probably in a few lines of code. And,those lines are
nothing special to frame here.
Surely, a non-keyed algorithm like ROT13 is not subject to anything, since
you can do it in your head. And such a posting is for education purposes,
at least for me, since it is the first C program I ever wrote.
I confess, I've been bad: I added ROT45, INV26, and INV90 sopistocated
algorithms to the program today, and found an error of mine: Not thinking,
I have stated that ROT45 behaves like ROT13 for UC letters, but it is true
instead for INV90 and INV26.
Aside from changing the name of the output file to be appropriate, the
nitty gritty for the algorithms is simply as follows:
switch(algorithm)
{case(1): //ROT13
{if((v1>64)&&(v1<78)){v2=v1+13;} //A-M
if((v1>77)&&(v1<91)){v2=v1-13;} //N-Z
if((v1>96)&&(v1<110)){v2=v1+13;} //a-m
if((v1>109)&&(v1<123)){v2=v1-13;} //n-z
break;}
case(2): //ROT45
{if((v1>32)&&(v1<78)){v2=v1+45;}
if((v1>77)&&(v1<123)){v2=v2-45;}
break;}
case(3): //INV26
{if((v1>64)&&(v1<91))
{v1=v1-64;v2=91-v1;} //A-Z
if((v1>96)&&(v1<123))
{v1=v1-96;v2=123-v1;} //a-z
break;}
case(4): //INV90
{if((v1>32)&&(v1<123))
{v1=v1-32;v2=123-v1;}
break;}
default:{cout<<endl<<"End!";}}
--
Let's all sit back an watch the inhabitants of the political zoo
perform in three rings. It's more exciting than soap operas. Then
vote out anyone who has been in long enough to abuse things.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: RSA Speed
Date: 16 Feb 2000 23:47:50 GMT
On Wed, 16 Feb 2000 15:23:45 -0500, Erik <[EMAIL PROTECTED]> wrote:
>I wrote a program to do RSA with a 1100 bit modulus. I use 65537 for
>the public key exponent, and the private key exponent is, of course,
>near 1100 bits. It works, and encrypting with the public key takes
>about a quarter of a second, but decrypting with the private key takes
>43 seconds on a 400 MHz Pentium. Does this seem right?
If you wrote the program in an interpreted language it might take that long.
A really carefully optimized assembler language implementation on a 400
mhz Pentium II or III (I'm assuming that's what you have since there was
no 400 mhz Pentium) should be able to decrypt in about 0.02 seconds.
A straightforward implementation written in C (something like RSAREF)
might take 0.5 seconds.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: OAP-L3 Encryption Software - Complete Help Files at web site
Date: Wed, 16 Feb 2000 13:01:52 -0000
Crossposted-To: talk.politics.crypto,alt.privacy
I still think my favorite part is that it "Uses no
mathematical equations" and yet still manages to perform
operationcs that are inherently mathematic
(encryption/decryption).
And of course some more gems.
on the page http://www.ciphile.com/soon.html
"with a key of less than 2,500 bytes ... a security
level equivalent to 10,000 bits"
5,000 bytes
..... 15,000 bits
10,000 bytes
..... 40,000 bits
50,000 bytes
...... 150,000 bits
If that's the case you have a serious problem, at least half
your bits are lost.
The more I read about OAP-L3 the more I find it stupendously
moronic.
"Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in
message news:[EMAIL PROTECTED]...
> OAP-L3: Original Absolute Privacy - Level3 Encryption
Software -
> Complete Help Files at web site
>
> Includes complete detailed explanation of entire
encryption
> software package: theory, operation, etc.
>
> http://www.ciphile.com
------------------------------
From: "Chuck Davis" <[EMAIL PROTECTED]>
Subject: code still unbroken
Date: Wed, 16 Feb 2000 15:59:00 -0800
Most of the correspondence I get from cryptanalysis folk about the code I
devised at discovervancouver.com sneers at its triviality. I still harbor a
belief that SOMEONE out there will crack it, and win the prize ... which
goes up one cent a minute, and is now well over $3,000.
Stifle your response to put down this Canadian layman's first effort and
actually try to SOLVE the damn thing. There are NO gimmicks.
Honest.
Really.
I swear.
I think it's rather elegant, actually.
Chuck Davis
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Wed, 16 Feb 2000 22:19:48 GMT
tiwolf wrote:
> Anything is possible given time, money, and talent.
Wrong, as has been explained several times now.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Question about OTPs
Date: Wed, 16 Feb 2000 22:35:02 GMT
Arthur Dardia wrote:
> So, my question is this: for one message, that I start at the
> 30,567,890 byte and the next I start at the 30,567,889. ...
That's horrible!
It is well known that reusing (portions of) the key makes a
one-time pad readily crackable. Here is a standard attack:
Step 1: Determine the relative offsets of the overlapping CT.
(This is easy with a so-called Kappa test, but in principle
you could just try each possible alignment; there aren't all
that many.)
Step 2: Difference the aligned CTs to strip off all effect of
the common key, leaving just the differenced PT ("delta stream").
Step 3: Try adding some probable plaintext to various offsets
within the delta stream; when the result is intelligible PT, you
have found portions of both original PTs.
Step 4: Extend the recovered PT fragments by reasonable
extrapolation past their ends; whenever you make a correct
extrapolation for one PT, you'll recover more of the *other*
PT (by the Step 3 process).
Step 5: When you can no longer extend either PT but more
remains, continue the search in Step 3.
In the above, "difference" and "add" depend on the system.
For the type of OTP usually discussed here, they're all XORs.
With only 2 PTs, sometimes one gets possible cross-overs in
the texts:
ATTACKATDAWN vs. ATTACKATNOON (2 other possibilities, also)
BEHEREBYNOON BEHEREBYDAWN
With a "stack" of several messages overlapping in the same
region of key, the extrapolation process goes very smoothly.
------------------------------
** 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
******************************
