Re: What are the DC instuctions buried in RSA in 3 lines of perl?

Adam Back (aba@dcs.ex.ac.uk)
Sun, 22 Mar 1998 15:19:07 -0500

• Next message: Matt Blaze: "Re: Rivest's Chaffing and Winnowing"
• Previous message: Bill Stewart: "Rivest's Chaffing and Winnowing"
• Next in thread: Perry E. Metzger: "Re: What are the DC instuctions buried in RSA in 3 lines of perl?"

Peter Junger <junger@samsara.LAW.CWRU.Edu> writes:
> In connection both with my law suit against the enforcement of theexport
> regulations relating to encryption software and with my course in
> computing and the law, I believe it would be a big help if I could
> understand the dc instructions that are implemented in Adam Back's
> version of RSA in two or three lines of perl.

The three line version is explained blow-by-blow at:

        http://www.dcs.ex.ac.uk/~aba/rsa/story.html

I never got around to documenting the 2 line version, but it's
similar, but only works with perl5, and has a few other tweaks.

Ken Pizzini (author of GNU dc, and contributor of many hacks) released
dc version 1.04 which has a modular exponentiation function |, so you
can do RSA like so:

M e N | P

(| is modular exponentiation using Knuth's algorithm). You might try
asking if you can export that because it is must surely be getting
close to the border line between arithmetic expression and program.
(It doesn't do the packing and unpacking... but if I recall you can do
it in nearly 1 line if you use dc-1.04.)

> I thus would be very grateful if anyone could tell me the actual set
> of dc instructions that are embedded in the perl code. And, for my
> own continuing education, I would also appreciate it if someone could
> tell me where I can find a simple explanation, with examples, on how to
> instruct the dc calculator.

dc is ok once you get used to it for arithmetic, the complexity arises
when you uses recursive dc functions, this can get interesting.

dc arithmetic equivalents compared to of ordinary arithmetic (in bc
syntax) examples are:

% bc
a = b * c;
^D

% dc
b c * sa
^D

(s is store, l is load, multiply is store args on stack then multiply
which leaves result on stack, sa stores the result on the stack into
a. To print a add lap (load variable a, and p is print)).

Next lets try b = 3, c = 4, a = b * c, print a:

% bc
b = 3; c = 4; a = b * c; print a;
12
^D

% dc
3sb 4sc lb lc * sa la p
^D

Simlarly for other arithmetic functions * / + - ^ (exponentiation) %
(modulus) all apply to the top two arguments on the stack; they remove
the top two arguments and replace them with the answer

% bc
print 3 * 4 + 2 ^ 3;
20
^D

% dc
3 4 * 2 3 ^ + P
^D

Now we come on to functions, say we want to write a function which
multiplies two numbers, and store that function in f:

% dc
[*]sf

(that's it, then use it)

3 4 lfxP
12

(lf is load f onto stack, x is execute the string f which is now on
the stack as a dc macro)

The rest is fiddling around with ways to save bytes, and recursive dc
macros to implement Knuth's modular arithmetic in as few bytes as
possible.

Adam

-- 
Now officially an EAR violation...
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`

• Next message: Matt Blaze: "Re: Rivest's Chaffing and Winnowing"
• Previous message: Bill Stewart: "Rivest's Chaffing and Winnowing"
• Next in thread: Perry E. Metzger: "Re: What are the DC instuctions buried in RSA in 3 lines of perl?"