Re: Ada & Encryption / Compression

Re: Ada & Encryption / Compression

[John Howard]

On 5 Mar 1997, David Downie wrote:
> I am thinking about writing an RSA encryption (or some other encryption)
> package. I would like to do it in Ada (rather than the suggested C), but
> am not an Ada expert and do not know if I would just be making things
> difficult for myself.
>
> Has anyone had any similar (bit level) experience and can comment or
> perhaps point me somewhere?

Forget about doing your own RSA encryption.
1)  RSA is patented.  You'd have to wait for the patent to expire.
2)  RSA can't be implemented unless you know the two large prime numbers
    it uses (which are a secret).  As of a year ago, RSA was still not
    reported as cracked to reveal the two primes.  Presumably many skilled 
    researchers have tried to crack RSA.

Forget about doing your own LZW compression.
1)  Lempel-Ziv Welch is not public domain.  LZW is used in GIF, TIFF, and
    Adobe PDF formats.
2)  Lempel-Ziv Huffman (LZH) is public domain.
3)  Run Length Encoding (RLE) is public domain.

See:

Digital Cash (Commerce on the Net), by Peter Wayner. Publ. by Academic
Press, 1996. PP. 271, Softcover, ISBN 0-12-738763-3.  [List: $34.95]

  One chapter explains RSA and DES and other schemes.  More an 
  introductory overview but with enough details for implementation by a 
  programmer who is equiped from elsewhere with large primes.


Differential Cryptanalysis of the Data Encryption Standard, by E. Biham &
A. Shamir. Publ. by Springer-Verlag, 1993.  PP. 188, Hardcover, ISBN 
0-387-97930-1. [List: $42.95, (North America only) sale price: $34.50 ends 
March 14; www.springer-ny.com]

  Tells how to crack some DES variants.  Useful to anyone implementing a
  sophisticated encryption scheme.


Alternatively, you can locate and download the Turbo Pascal sources from 
SWAG (source ware archive group).  It has a few simple encryption and 
compression examples.  You could recode these as filters for Ada 95 
streams.  (SWAG IS SEVERAL MEGABYTES UNCOMPRESSED)

Lastly there is stream specific source code in Turbo Pascal (not related 
to SWAG).  Filename: streams13.zip or higher.  Streams implements about a 
dozen filters and a few perform simple encryption or compression.

Translating a couple Turbo Pascal filters into Ada 95 filters is feasible 
for an intermediate-level programmer.

[For simple encryption use a filter employing XOR operation and a linear 
congruential "random" number generator based upon the position within the
stream and the direction state.  This allows for encryption while moving 
backward or forward within the stream.

For sophisticated encryption use a DES variant as a filter.

For loss-less compression use LZH and RLE as filters.]

-- John Howard <jhoward@sky.net>               -- Team Ada  Team OS/2 --

Re: Ada & Encryption / Compression

[Norman H. Cohen]

David Downie wrote:
 
> I am thinking about writing an RSA encryption (or some other encryption)
> package. I would like to do it in Ada (rather than the suggested C), but
> am not an Ada expert and do not know if I would just be making things
> difficult for myself.

Bit manipulation is as easy with Ada-95 modular types as with C.  If
you're using Ada 83 instead of Ada 95, you have to write unchecked
conversions to and from packed arrays of booleans, which is a mild
nuisance, but not a serious obstacle.

By using Ada instead of C, you are most likely making things easier for
yourself, because Ada's compile-time and run-time checks will reduce
your debugging effort.

-- 
Norman H. Cohen
mailto:ncohen@watson.ibm.com
http://www.research.ibm.com/people/n/ncohen

Ada & Encryption / Compression

[David Downie]

I am thinking about writing an RSA encryption (or some other encryption)
package. I would like to do it in Ada (rather than the suggested C), but
am not an Ada expert and do not know if I would just be making things
difficult for myself.

Has anyone had any similar (bit level) experience and can comment or
perhaps point me somewhere? 

Thanks,

David. 

Re: Ada & Encryption / Compression

[Laurent Pautet]

>>>>> "David" == David Downie <cs323389@student.uq.edu.au> writes:

David> I am thinking about writing an RSA encryption (or some other
David> encryption) package. I would like to do it in Ada (rather than
David> the suggested C), but am not an Ada expert and do not know if I
David> would just be making things difficult for myself.

David> Has anyone had any similar (bit level) experience and can
David> comment or perhaps point me somewhere?

Data filtering (basically compression) will be available in the next
GLADE release (Ada binding to Z library). At the same time, as it is
possible to add other filters, contributors will provide encryption
filters (wolf@lglsun.epfl.ch).

Re: Ada & Encryption / Compression

[Bob Klungle]

Bit level operations are part of the Interfaces package in Ada95. Much
easier than in Ada83. Go for it. Might learn a lot.

cheers...bob

> I am thinking about writing an RSA encryption (or some other encryption)
> package. I would like to do it in Ada (rather than the suggested C), but
> am not an Ada expert and do not know if I would just be making things
> difficult for myself.
> 
> Has anyone had any similar (bit level) experience and can comment or
> perhaps point me somewhere? 

Re: Ada & Encryption / Compression

[Larry Kilgallen]

In article <Pine.GSO.3.93.970305115055.7933B-100000@sky.net>, John Howard <jhoward@sky.net> writes:

> Forget about doing your own RSA encryption.

Ok, you got my attention.

> 1)  RSA is patented.  You'd have to wait for the patent to expire.

	a. comp.lang.ada has international circulation.  RSA is only
	   patented in the United States.  Even if the original poster
	   was in the United States (not always obvious from email
	   addresses) or planned to do the work in the United States
	   (totally unknown absent a specific statement), there are
	   many others who will read your comments who are not in the
	   United States.

	b. Contrary to what you imply, the fact that something is
	   patented does not prevent you from using it.  it means
	   that using it requires obtaining a license from the
	   holder of the patent or their authorized representative.
	   In the case of RSA, the patent holder (actually, assignee)
	   is the Massachusetts Institute of Technology and the
	   authorized representative for licenses is RSA Data Security
	   Incorporated in Redwood Shores California.  Their general
	   web address for a patent license is:

		http://www.rsa.com/rsa/contracts/PatLicAgree.html

	   but I notice it is down today.  Those interested in the
	   general range of charges for a license could certainly
	   contact RSA Data Security Incorporated by other means.

> 2)  RSA can't be implemented unless you know the two large prime numbers
>     it uses (which are a secret).

	c. The RSA algorithm can use any two large prime numbers,
	   and the numbers are made up by the person who will be
	   using the RSA algorithm (with the help of a computer).

>                                    As of a year ago, RSA was still not
>     reported as cracked to reveal the two primes.  Presumably many skilled 
>     researchers have tried to crack RSA.

	d. That is the good part, unless the original poster said
	   his goal was to _break_ RSA.  When people say they are
	   going to _use_ RSA, they generally mean they are going
	   to make up their own prime numbers and take advantage
	   of the fact that there are no easy methods of breaking
	   RSA.  "Easy" is related to the size of the prime numbers
	   chosen, and a 129 digit (500 bits or so) challenge has
	   been broken so contemporary wisdom is to use 1024 bits
	   or so, except for the truly paranoid (the master key for
	   VISA as an example) where 2048 bits is used. Absent an
	   astounding breakthrough in factoring techniques, those
	   who discuss the adequacy of key size in relation to
	   Moore's Law (expanding computer potential) do so in terms
	   of how much longer it would take than the predicted remaining
	   life of the universe.  All such approaches presume massively
	   parallel efforts.

Sorry to go on so long, but I hate egregious misinformation.
Now I know how Robert Dewar feels with a typical day on c.l.a.

Larry Kilgallen

Re: Ada & Encryption / Compression

[David L Brown]

John Howard <jhoward@sky.net> writes:

> Forget about doing your own RSA encryption.
> 1)  RSA is patented.  You'd have to wait for the patent to expire.

Agreed, and this might be enough to stop you.  RSA claims that you can
only use their implementation.  You could probably call the C just
fine from Ada.  (I don't know if it is available outside of the US,
PGP uses the code, and is available outside of the US).

> 2)  RSA can't be implemented unless you know the two large prime numbers
>     it uses (which are a secret).  As of a year ago, RSA was still not
>     reported as cracked to reveal the two primes.  Presumably many skilled 
>     researchers have tried to crack RSA.

Hmm?  The secret key is something that I generate.  I tell someone the
product of these two primes which they can use to encrypt, but I need
to know the factors in order to decrypt.

Don't confuse the RSA algorithm with the contest that RSA is holding
to crack a particular key.  They are witholding this key, not because
it has to do with the algorithm, but because it is part of a contest.

Please see <http://www.rsa.com/>

I do not speak for RSA,
David Brown
dbrown@vigra.com

Re: Ada & Encryption / Compression

[Larry Kilgallen]

In article <osn2shxb7e.fsf@ted.vigra.com>, David L Brown <dbrown@ted.vigra.com> writes:
> John Howard <jhoward@sky.net> writes:
> 
>> Forget about doing your own RSA encryption.
>> 1)  RSA is patented.  You'd have to wait for the patent to expire.
> 
> Agreed, and this might be enough to stop you.  RSA claims that you can
> only use their implementation.

In former years, RSA did not license the patent for your own
implementation other than with a very steep minimum fee (on
the order of 10 million dollars, according to rumor).   That
is now different, and prices for your own implementation are
down to something reasonable (in my view).

>                                 You could probably call the C just
> fine from Ada.

In my opinion calling RSA's BSAFE toolkit from Ada is much nicer
than calling it from C.  Of course I might say that about a lot
of toolkits, but even though it is written in C, BSAFE avoids
such C-isms as null-terminated strings.

> Don't confuse the RSA algorithm with the contest that RSA is holding
> to crack a particular key.  They are witholding this key, not because
> it has to do with the algorithm, but because it is part of a contest.

Ah, that explains the original comment. I couldn't understand the basis.

Of course the currently publicized contests sponsored by RSA are
not for the RSA algorithm at all (where an ongoing contest ran
for 10 years) but for block ciphers, in particular DES and RC5.
Although RC5 is a development or RSA Data Security Inc. (patent
applied for) it is not the "RSA" public key algorithm.  It is a
secret key algorithm (the "other kind"), as is DES.

Larry Kilgallen

Re: Ada & Encryption / Compression

[William W Pritchett]

Larry Kilgallen (kilgallen@eisner.decus.org) wrote:

: In my opinion calling RSA's BSAFE toolkit from Ada is much nicer
: than calling it from C.  Of course I might say that about a lot
: of toolkits, but even though it is written in C, BSAFE avoids
: such C-isms as null-terminated strings.

I have a requirement to use BSafe with Ada and was wondering if anyone
has done an Ada 95 binding to the product.

Thanks,
Bill Pritchett

Re: Ada & Encryption / Compression

[Laurent Pautet]

>>>>> "Larry" == Larry Kilgallen <kilgallen@eisner.decus.org> writes:

    Larry> In former years, RSA did not license the patent for your
    Larry> own implementation other than with a very steep minimum fee
    Larry> (on the order of 10 million dollars, according to rumor).

First of all, Larry thanks for your previous post and all these clarifications.

    Larry> In my opinion calling RSA's BSAFE toolkit from Ada is much
    Larry> nicer than calling it from C.  Of course I might say that
    Larry> about a lot of toolkits, but even though it is written in
    Larry> C, BSAFE avoids such C-isms as null-terminated strings.

Yes, we choose this solution for the GLADE filtering (RSA + DES), but
of course, you have to check that the implementation is thread-safe if
needed.

BSAFE Bindings for Ada (was: Ada & Encryption / Compression)

[Larry Kilgallen]

In article <5fn9fu$r04@portal.gmu.edu>, wpritche@osf1.gmu.edu (William W Pritchett) writes:
> Larry Kilgallen (kilgallen@eisner.decus.org) wrote:
> 
> : In my opinion calling RSA's BSAFE toolkit from Ada is much nicer
> : than calling it from C.  Of course I might say that about a lot
> : of toolkits, but even though it is written in C, BSAFE avoids
> : such C-isms as null-terminated strings.
> 
> I have a requirement to use BSafe with Ada and was wondering if anyone
> has done an Ada 95 binding to the product.

It may be that our OEM agreement with RSA prohibits sharing that,
but perhaps something could be worked out for me to mail bindings
to your RSA sales representative for passing on to you.

But those would be Ada 83 bindings, possibly requiring platform-
specific tuning.  Send mail if there is possible future interest
and I will ensure there is a "presentable" set of bindings ready
for transfer.

Larry Kilgallen

Re: Ada & Encryption / Compression

[Ronald Cole]

kilgallen@eisner.decus.org (Larry Kilgallen) writes:
> In article <Pine.GSO.3.93.970305115055.7933B-100000@sky.net>, John Howard <jhoward@sky.net> writes:
> > Forget about doing your own RSA encryption.
> > 1)  RSA is patented.  You'd have to wait for the patent to expire.
> 
> 	a. comp.lang.ada has international circulation.  RSA is only
> 	   patented in the United States.

The patent (#4,405,829) expires in the US on September 20, 2000.

-- 
Forte International, P.O. Box 1412, Ridgecrest, CA  93556-1412
Ronald Cole <ronald@ridgecrest.ca.us>    Phone: (619) 499-9142
President, CEO                             Fax: (619) 499-9152
My PGP fingerprint: E9 A8 E3 68 61 88 EF 43  56 2B CE 3E E9 8F 3F 2B

Re: Ada & Encryption / Compression

[John Howard]

On Thu, 6 Mar 1997, Larry Kilgallen wrote:
> In article <osn2shxb7e.fsf@ted.vigra.com>, David L Brown
> <dbrown@ted.vigra.com> writes:
> > John Howard <jhoward@sky.net> writes:
> >> Forget about doing your own RSA encryption.
> >> 1)  RSA is patented.  You'd have to wait for the patent to expire.
> >
> > Agreed, and this might be enough to stop you.  RSA claims that you can
> > only use their implementation.

I presumed his circumstances would dictate forcing his implementation to 
be compatible with some standardized implementation offered by RSA.

> In former years, RSA did not license the patent for your own
> implementation other than with a very steep minimum fee (on
> the order of 10 million dollars, according to rumor).   That
> is now different, and prices for your own implementation are
> down to something reasonable (in my view).

I incorrectly assumed everyone must license RSA technology even if they
use their own prime numbers.  From his address and generalized question I
assumed he is a college student in Australia probably looking to do a
senior design project.  I presumed his college would not spend the money 
to acquire an RSA license even as an investment in a standardized 
implementation.  So I suggested he start simple and possibly later add a
DES variant (which presumably he would not be required to obtain a license
to implement).

[snip]
> > Don't confuse the RSA algorithm with the contest that RSA is holding
> > to crack a particular key.  They are witholding this key, not because
> > it has to do with the algorithm, but because it is part of a contest.
>
> Ah, that explains the original comment. I couldn't understand the basis.

Nope.  My comments were unrelated to any contest.  I tried to convey that
he had little chance of discovering the prime numbers used in a standard
implementation offered by RSA.  In my reasoning, as explained above, that 
left the "unlikely" event of him licensing and binding to an 
implementation authorized by RSA.  You two have since pointed out that 
event is not so unlikely for the rest of us.  But if this is to be the 
focus of a senior design project then I believe it is less likely for him
because he'll simply be interfacing to a canned implementation.  He'll 
probably need more to base a grade on.

[snip]
> Larry Kilgallen

I think the discussion has been very useful.  There is one issue left open
that should be closed though:
1)
  Is a license required (working within the U.S.) to implement (for the
  U.S. market) the RSA public key algorithm with ones own prime numbers?
  A. Always yes.
  B. Always no.
  C. Sometimes.
  D. Don't know.

2)
  Is a license required (working outside the U.S.) to implement (for the 
  U.S. market) the RSA public key algorithm with ones own prime numbers?
  A. Always yes.
  B. Always no.
  C. Sometimes.
  D. Don't know.

I don't have useful answers to these.  Luckily, I don't have to know.

-- John Howard <jhoward@sky.net>               -- Team Ada  Team OS/2 --

Re: Ada & Encryption / Compression

[Larry Kilgallen]

In article <Pine.GSO.3.93.970307143338.7386A-100000@sky.net>, John Howard <jhoward@sky.net> writes:

> 1)
>   Is a license required (working within the U.S.) to implement (for the
>   U.S. market) the RSA public key algorithm with ones own prime numbers?
>   A. Always yes.
>   B. Always no.
>   C. Sometimes.
>   D. Don't know.
>
> 2)
>   Is a license required (working outside the U.S.) to implement (for the 
>   U.S. market) the RSA public key algorithm with ones own prime numbers?
>   A. Always yes.
>   B. Always no.
>   C. Sometimes.
>   D. Don't know.

"Prime Numbers" is irrelevant, as those are made up by end users (with
the help of software or hardware) in any trustworthy implementation.
If you substitute "code" for "prime numbers", the answer is A for
both cases.  The key phrase is "for the U.S. market".

Larry Kilgallen

Re: Ada & Encryption / Compression

[Robert Dewar]

Larry says

<<"Prime Numbers" is irrelevant, as those are made up by end users (with
the help of software or hardware) in any trustworthy implementation.
If you substitute "code" for "prime numbers", the answer is A for
both cases.  The key phrase is "for the U.S. market".>>

Has this patent been successfuly litigated? Remember that the existence
of a patent per se does NOT mean that license fees have to be paid. They
have to be paid only if the patent is valid. The fact that the patent
office accepts a patent is an a priori suggestion that at least omeone
in the patent office thought it might be valid, but until it is litigated
no one can say for sure. For my taste the RSA claims are *awfully* broad,
but I have not followed the progress of this patent in any detail.

Re: Ada & Encryption / Compression

[Robert Dewar]

<<"Prime Numbers" is irrelevant, as those are made up by end users (with
the help of software or hardware) in any trustworthy implementation.
If you substitute "code" for "prime numbers", the answer is A for
both cases.  The key phrase is "for the U.S. market".
>>

Most countries have bilateral agrements to repsect one anothers patents,
so it is not the case that patents in the US apply to the US only.

Re: Ada & Encryption / Compression

[Robert Dewar]

<<I don't know exactly how you define "litigated", but several cases have
been filed and none have gone to trial but instead have ended in out of
court settlements which involved royalties being paid to RSADSI.  While
the claims may seem overbroad to a computer person such as yourself, it
would appear there is a different opinion from lawyers who actually got
involved in specific cases.>>

I mean that a court has ruled the patent valid. The fact that someone
is willing to pay a license fee, or that their lawyer advises them to
pay the fee absolutely does NOT mean the patent is valid, or that the
lawyer thinks that it is valid. More often it means that the license
fee agreed on is low enough that it is not worth the expense, and particularly
the time delay and risk, of challenging the patent. Most usually these
settlements are kept secret, and in particular the amount of the settlement
is kept secret. Very often a weak patent ends up surviving simply because
the holder knows it is weak, and asks for royalties at a level where it
is cheaper to pay than fight. 

And of course big companies all have interlocking patent sharing agreements
anyway, and an interest in having their patents be considered valid, so
they have in an interest in NOT challenging one another's patents, since
very often the only purpose of patents is to enable large players to stop
small players out of the playing field. Whether this meets the burden
placed upon patent law by the commerce clause of the consitution, I will
leave up to the reader :-)

Re: Ada & Encryption / Compression

[Larry Kilgallen]

In article <dewar.857858068@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:
> <<"Prime Numbers" is irrelevant, as those are made up by end users (with
> the help of software or hardware) in any trustworthy implementation.
> If you substitute "code" for "prime numbers", the answer is A for
> both cases.  The key phrase is "for the U.S. market".
>>>
> 
> Most countries have bilateral agrements to repsect one anothers patents,
> so it is not the case that patents in the US apply to the US only.

All parties involved in this patent agree that it is US-only.  One story
is that there is (or was at the time) a filing deadline for various of
the European countries which was missed.  Another is that some countries
require (or required) filing before publication whereas in the US it is
(or was) within one year after publication.  This is a chicken-and-the-egg
problem in the area of crypto, since if you file for a US patent prior to
publication the government (NSA) has the opportunity of declaring your new
technique classified and forbidding you to use or talk about it in public.
If the NSA had the opportunity starting with the Diffie-Hellman paper, they
would have nipped public-key crypto in the bud.  Please let us not start a
discussion about whether they should have or would today, but that was their
behaviour at the time.  It's just very hard to "unpublish" an article from
Communications of the ACM and you get unfavorable news coverage of the book
burnings.

Larry Kilgallen

Re: Ada & Encryption / Compression

[Larry Kilgallen]

In article <dewar.857857945@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Has this patent been successfuly litigated? Remember that the existence
> of a patent per se does NOT mean that license fees have to be paid. They
> have to be paid only if the patent is valid. The fact that the patent
> office accepts a patent is an a priori suggestion that at least omeone
> in the patent office thought it might be valid, but until it is litigated
> no one can say for sure. For my taste the RSA claims are *awfully* broad,
> but I have not followed the progress of this patent in any detail.

I don't know exactly how you define "litigated", but several cases have
been filed and none have gone to trial but instead have ended in out of
court settlements which involved royalties being paid to RSADSI.  While
the claims may seem overbroad to a computer person such as yourself, it
would appear there is a different opinion from lawyers who actually got
involved in specific cases.

I am not at all saying that the points involved in the cases which were
filed are the same as the points which you find overbroad.   I have not
read the patent but it may contain language which might be construed as
applicable to Elliptic Curve techniques. I do not know that cases which
have been filed involved Elliptic Curve techniques.

Larry Kilgallen