A new section is available on http://www.dataheaven.de.
It is called "Cryptography in CommonLisp".
I've posted two little modules - the first contains some often needed
mathematic functions for cryptography like:
- expt-mod (fast modular exponentation)
- primep (Miller Rabin Pseudoprime test)
- extended-gcd
- multiplicative-inverse-mod ( a^-1 mod n )
The second module contains an implementation of the RSA algorithm with
the following functionality:
- Generation of RSA keys
- Encryption/Decryption
- Signing and Validation of messages
As usual you will find the code on http://www.dataheaven.de
Regards,
Jochen Schmidt
On Mon, 16 Apr 2001 10:48:10 +0200, Jochen Schmidt <···@dataheaven.de> wrote:
>A new section is available on http://www.dataheaven.de.
>It is called "Cryptography in CommonLisp".
>I've posted two little modules - the first contains some often needed
>mathematic functions for cryptography like:
<Snip>
Thank you, Jochen Schmidt, for making your work public. I'm sure that
I'm not the only one in the community that appreciates it.
I do have a question, one that is probably more directed toward the
clisp developers than yourself, but you may already have the answer to
it.
When I run the following set of commands under clisp (including both the
stable and current sources) I get a divide by zero error:
(load "math.lisp")
(load "rsa.lisp")
(in-package :cipher.rsa)
(generate-rsa-key 1024)
Can anyone explain what is happening here?
The code works fine under ACL4.0. Unfortunately my skills at debugging
Lisp code with the tools I have available are still lacking. I wish
there was a document on the web that went through the basic principles
used in debugging Lisp code using a freely available Lisp system (such
as clisp). Despite the stories I read, I still find my C code at least
as easy to debug as my Lisp code. This is in large part due to my
better understanding of the environment and the better tools I have
available.
Thanks,
--
Kenneth P. Turvey <······@SprocketShop.com>
--------------------------------------------------------
/"\
\ / ASCII RIBBON CAMPAIGN
X AGAINST HTML MAIL AND NEWS
/ \
Kenneth P. Turvey wrote:
> On Mon, 16 Apr 2001 10:48:10 +0200, Jochen Schmidt <···@dataheaven.de>
> wrote:
>>A new section is available on http://www.dataheaven.de.
>>It is called "Cryptography in CommonLisp".
>>I've posted two little modules - the first contains some often needed
>>mathematic functions for cryptography like:
> <Snip>
>
> Thank you, Jochen Schmidt, for making your work public. I'm sure that
> I'm not the only one in the community that appreciates it.
>
> I do have a question, one that is probably more directed toward the
> clisp developers than yourself, but you may already have the answer to
> it.
>
> When I run the following set of commands under clisp (including both the
> stable and current sources) I get a divide by zero error:
>
> (load "math.lisp")
> (load "rsa.lisp")
> (in-package :cipher.rsa)
> (generate-rsa-key 1024)
>
> Can anyone explain what is happening here?
Yes - the problem is that it seems that CLISP doesn't like my LOOP in
CIPHER.MATH:EXTENDED-GCD
(defun extended-gcd (a b)
"if d = gcd(a,b) then there is a x and b y so that d = ax + by. Returns d
x and y."
(loop for x = 1 then x2
and y = 0 then y2
and d = a then d2
and x2 = 0 then (- x (* k x2))
and y2 = 1 then (- y (* k y2))
and d2 = b then (- d (* k d2))
until (zerop d2)
for k = (floor d d2)
finally (return (values d x y))))
If you evaluate this function in CLISP, it warns that a FOR should be
before the loop body. So the problem here is that CLISP dislikes the FOR
clause after my UNTIL clause (Or the other way round) so that it does the
(FLOOR d d2) when d2 is already ZEROP.
I do not know if I'am doing illegal LOOPing here but it seems to work in
CMUCL, LispWorks and ACL.
For the meantime you can use this patched version
(defun extended-gcd (a b)
"if d = gcd(a,b) then there is a x and b y so that d = ax + by. Returns d
x and y."
(loop with k = 0
for x = 1 then x2
and y = 0 then y2
and d = a then d2
and x2 = 0 then (- x (* k x2))
and y2 = 1 then (- y (* k y2))
and d2 = b then (- d (* k d2))
do (if (zerop d2)
(return (values d x y))
(setf k (floor d d2)))))
If you use this function your example goes fine and gives you a 1024 bit
RSA-key in somewhere around 5 seconds on a K6-2 300 Mhz.
But think that the code is not using a proper random-source (like
/dev/random in Linux, FreeBSD, and OpenBSD)
> The code works fine under ACL4.0. Unfortunately my skills at debugging
> Lisp code with the tools I have available are still lacking. I wish
> there was a document on the web that went through the basic principles
> used in debugging Lisp code using a freely available Lisp system (such
> as clisp). Despite the stories I read, I still find my C code at least
> as easy to debug as my Lisp code. This is in large part due to my
> better understanding of the environment and the better tools I have
> available.
You find the above Error if you type in "backtrace" (without the quotes)
after the division-by-zero pops up. This will show you the call-stack until
the error happens starting with the most recent form. (In this case the
(FLOOR d d2) )
So the first you see is that the error occured in a form named "(FLOOR d
d2"). Then you go down and lokk for the function-call that "contained" this
form, which is in this case EXTENDED-GCD. Then you go to the definition of
this function and look for the form (FLOOR d d2). The rest is just thinking
work... ;-)
Regards,
Jochen
--
···@dataheaven.de
http://www.dataheaven.de
On Tue, 24 Apr 2001 20:54:53 +0200, Jochen Schmidt <···@dataheaven.de> wrote:
>
>Yes - the problem is that it seems that CLISP doesn't like my LOOP in
>CIPHER.MATH:EXTENDED-GCD
>
>(defun extended-gcd (a b)
> "if d = gcd(a,b) then there is a x and b y so that d = ax + by. Returns d
[Snip]
Thanks for the patch. I saw the warning, but I didn't really see how
that would lead to a divide by zero error... as I said my debugging
skills in Lisp could use some work.
>But think that the code is not using a proper random-source (like
>/dev/random in Linux, FreeBSD, and OpenBSD)
This is easy enough to fix. I can write a platform dependent substitute
for RANDOM without much difficulty (assuming one doesn't already exist).
Speaking of this, do any of the other Lisp implementations produce
good random numbers?
>> The code works fine under ACL4.0. Unfortunately my skills at debugging
>> Lisp code with the tools I have available are still lacking. I wish
>> there was a document on the web that went through the basic principles
>> used in debugging Lisp code using a freely available Lisp system (such
>> as clisp). Despite the stories I read, I still find my C code at least
>> as easy to debug as my Lisp code. This is in large part due to my
>> better understanding of the environment and the better tools I have
>> available.
>
>You find the above Error if you type in "backtrace" (without the quotes)
>after the division-by-zero pops up. This will show you the call-stack until
>the error happens starting with the most recent form. (In this case the
>(FLOOR d d2) )
>So the first you see is that the error occured in a form named "(FLOOR d
>d2"). Then you go down and lokk for the function-call that "contained" this
>form, which is in this case EXTENDED-GCD. Then you go to the definition of
>this function and look for the form (FLOOR d d2). The rest is just thinking
>work... ;-)
I'm going to work through this and see how it comes together. Thanks
for the pointer.
--
Kenneth P. Turvey <······@SprocketShop.com>
--------------------------------------------------------
The world is full of fools and faint hearts; and yet everyone has
courage enough to bear the misfortunes, and wisdom enough to manage
the affairs, of his neighbor. -- Benjamin Franklin
From: Ralf Muschall
Subject: Re: ANN: Cryptography for Common Lisp (some utility-functions+ RSA)
Date:
Message-ID: <m34rvc1udr.fsf@mammut.lipsia.de>
······@SprocketShop.com (Kenneth P. Turvey) writes:
> This is easy enough to fix. I can write a platform dependent substitute
> for RANDOM without much difficulty (assuming one doesn't already exist).
I'd say that this is hard unless you're a kernel hacker (essentially,
you have to *access*, not to *write* a random source (the latter is
impossible)). Opening /dev/random and eating bytes from there is easy
on machines which have that, otherwise you will end up either md5ing
the output of ps(1) etc., or repeating (part of) the work the kernel
hackers did when they made /dev/random. Stealing the egd (entropy
gathering demon, comes with gnupg) might help for the first method.
> Speaking of this, do any of the other Lisp implementations produce
> good random numbers?
I'd guess most of them have (*random-state* is a variable of an opaque
type, i.e. at least we don't have to expect crap like x:=3*x+5 mod 17).
Ralf
--
GS d->? s:++>+++ a C++++ UL+++ UH++ P++ L++ E+++ W- N++ o-- K- w--- !O M- V-
PS+>++ PE Y+>++ PGP+ !t !5 !X !R !tv b+++ DI+++ D? G+ e++++ h+ r? y?
On 26 Apr 2001 00:34:24 +0200, Ralf Muschall <····@lipsia.de> wrote:
>······@SprocketShop.com (Kenneth P. Turvey) writes:
>
>> This is easy enough to fix. I can write a platform dependent substitute
>> for RANDOM without much difficulty (assuming one doesn't already exist).
>
>I'd say that this is hard unless you're a kernel hacker (essentially,
>you have to *access*, not to *write* a random source (the latter is
>impossible)). Opening /dev/random and eating bytes from there is easy
>on machines which have that, otherwise you will end up either md5ing
>the output of ps(1) etc., or repeating (part of) the work the kernel
>hackers did when they made /dev/random. Stealing the egd (entropy
>gathering demon, comes with gnupg) might help for the first method.
What I was really implying was a version of RANDOM that used
a platform dependent source of random bits to generate the random
numbers where available. Using egd isn't a bad idea however. I'll look
into it.
--
Kenneth P. Turvey <······@SprocketShop.com>
--------------------------------------------------------
If you pick up a starving dog and make him prosperous, he will not
bite you. This is the principal difference between a man and a dog.
-- Mark Twain
From: Ralf Muschall
Subject: Re: ANN: Cryptography for Common Lisp (some utility-functions+ RSA)
Date:
Message-ID: <m38zkkxxsi.fsf@mammut.lipsia.de>
······@SprocketShop.com (Kenneth P. Turvey) writes:
> What I was really implying was a version of RANDOM that used
> a platform dependent source of random bits to generate the random
I'd call such a beat differently from "RANDOM". The latter is
expected by people to generate fast pseudorandom numbers, whereas a
true entropy source is usually expensive. Otherwise lusers might
end up calling your "RANDOM" in monte-carlo-simulations :-)
Ralf
--
GS d->? s:++>+++ a C++++ UL+++ UH++ P++ L++ E+++ W- N++ o-- K- w--- !O M- V-
PS+>++ PE Y+>++ PGP+ !t !5 !X !R !tv b+++ DI+++ D? G+ e++++ h+ r? y?