RSA
Version 1.2b
TURBO Pascal (tm)
October 14, 1984
D.M. Fritz-Rohner
P.O. Box 9080
Akron, Ohio 44305
RSASetUp, RSACrypt, and RSAClear may be used for
noncommercial purposes only. No commercial use
of this document or these programs may be made
without the author's express written permission.
The programs RSASetUp 1.2b, RSACrypt 1.1b, and RSAClear 1.1e
implement a version of the Rivest-Shamir-Adleman (1) approach to
public key cryptography using TURBO Pascal 2.0 (tm) and intend
ed to run in CP/M 2.2 (tm) environments. These versions super
cede, but do not obsolete, earlier releases.
The following discussion and the subroutines in these pro
grams depend on Knuth (2). Another introduction to this subject
is found in Smith (3) with BASIC routines presented there avail-
able in the PKS10/M.LBR library on some bulletin board systems.
The object files were produced in a configuration such that
the indispensable utility EX or a convenient command extension,
like microShell (tm), may be used to facilitate I/O. These
versions were compiled with a TURBO Options END address suitable
to operation in an MP/M environment.
ILLUSTRATION
Pick two prime numbers, say, 3 and 11 and call them 'p' and 'q';
p = 3
q = 11
Multiply these numbers to form a 'public' product number 'n';
n = p x q = 33
Decrement each of the prime numbers and form the 'private' pro
duct number;
n' = (p-1) x (q-1) = 2 x 10 = 20
Find a number relatively prime to this number, i.e., does
not share any factors with it. In this case the private product
number may be factored;
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
n' = 2 x 2 x 5
so that 3, 7, 9, 11, 13, 17, 19, or 21, etc. might be used as a
'key'. Then find a number that multiplied by this number and the
product divided by n' the remainder is 1. That is, find the
reciprocal of the key modulo n'. The corresponding reciprocals
are 7, 3, 9, 11, 17, 13, 19, 21, etc. Pick one of these, say 3,
as the public key, then the private key is 7;
(d,d') = (3,7)
with the other possible choices (7,3), (9,9), (11,11), (13,17),
(17,13), (19,19), (21,21), etc. Now publish the numbers d and n.
These numbers are used to encrypt. Keep d' private. Note the
unattractive 'square roots' and the mutually complementary pairs.
Someone wishes to send the message, 'HELP', to you. They
encode the message using numbers with values in the range
[0,(n-1)]. For example, let A = 32, B = 31, ..., Z = 7. And
let 6 = EOM, denote end of message. So that;
c , c , c , c , c = H, E, L, P, EOM = 25, 28, 21, 17, 6
1 2 3 4 5
Then form the sequence;
d
e , e , e , e , e where e = c mod n
1 2 3 4 5 i i
That is,
d 3
e = c mod n = 25 mod 33
1 1
d 3
e = c mod n = 28 mod 33
2 2
...
d 3
e = c mod n = 6 mod 33
5
So the encrypted message sent to you is;
e , e , e , e , e = 16, 7, 21, 29, 18
1 2 3 4 5
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
To decrypt the message requires application of the corre
sponding transformation;
d'
c = e mod n
i i
where d' is the 'private' key. That is;
7
c = 16 mod 33
1
7
c = 7 mod 33
2
...
7
c = 18 mod 33
5
Which yields the original sequence;
25, 28, 21, 17, 6 = H, E, L, P, EOM
RSA SetUp Application
=====================
The program RSASetUp supports generation and testing of
public and private product numbers and keys. This particular
release uses radix 10 so that all numbers appearing in the
examples are decimal.
Input to the program consists of five random numbers pro-
vided by the user. These numbers are used to initiate the search
for prime factors with particular properties.
The first two numbers are used to find 'p', the second two
to find 'q', and the last number to find 'd'. The random numbers
for generation of 'p' and 'q' are constrained to fewer than 64
digits each to help assure that the TURBO string type length is
not exceeded. The random number used to initiate the search for
d may be up to 255 digits.
Following Knuth (2) we choose numbers to assure that p and
q are not 'close'. This release uses the TURBO Random function
to generate the test numbers required by the probabilistic pri
mality test (2). See COMMENT section below.
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
EXAMPLE 1
The random numbers were generated by drawing with replace
ment using ordinary playing cards with face cards and jokers
removed and values taken modulo 10;
p1: 15378645
p2: 7223
q1: 569011
q2: 760
d0: 90854
The following is an annotated dialogue with RSASetUp using
these numbers;
A>rsasetup <- Command.
Initialize: .. Be patient.
Compose p:
r1: 15378645 <- Input 1st random number.
15378645* .. Search downwards for prime.
.. Each * denotes a probabilistic
.. primality test.
15378641****** .. Found p1.
r2: 7223 <- Input 2nd random number, p2.
111218331713* .. Form k, k >= p2, k even and
.. congruent p1 mod 3.
.. Find prime of form k*p1+1.
111310603559* .. Search upwards on even k.
111495147251******** .. Found p.
2 2 3 601 15459671 .. Try factoring p+1 over
.. 'small' primes.
Compose q:
r1: 569011 <- Input 3rd random number, q1.
569011***** .. Found q1!
r2: 760 <- Input fourth random number, q2.
432448361* .. Form k and search for same
439276493* .. form as for p.
442690559*
449518691*
452932757*
456346823******* .. Found q.
2 2 2 3 19014451 .. Try to factor q+1.
Factor p: 111495147251 .. Summary.
Factor q: 456346823
Product Number: 50880456227911033573 .. Product number n.
Compose d:
d0: 90854 <- Input 5th random number.
90855 .. Search for prime relative to
90857 .. p and q.
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Public Key: 90859 .. Found d.
Private Key: 31150762526139197039 .. Compute d' so that
.. d*d' mod (p-1)*(q-1) = 1.
This process required 3 min 41 sec using a 4MHz Z-80 based system.
EXAMPLE 2
For the numbers;
p1: 83798947449192
p2: 8037159836
q1: 6702836446
q2: 316702
d0: 3
the following is the excerpted dialogue;
Factor p: 673505540938802518493171
Factor q: 2123404954847849
Product Number: 1430125002746934077975498693071050539179
Public Key: 3
Private Key: 953416668497955602979970420575718132107
the generation of which required 12 min 56 sec.
EXAMPLE 3
Numbers used in CHALLENGE, see below.
EXAMPLE 4
For the numbers;
p1: 15518583779449518110039545577
p2: 5222145577922089217
q1: 6008824107816112004
q2: 1726939819690
d0: 5192368
the following is the excerpted dialogue;
Factor p: 81040303659465766099166750150404239070782928601
Factor q: 10376877623139581707321200412109
Product Number: 8409453136163470643156122058544049639514153768
29479649746062737794923122829509
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Public Key: 5192369
Private Key: 6282552011668134376062956068120081882940185484158
37484526862877770664065862929
the generation of which required 2 hr 11 min 32 sec.
EXAMPLE 5
For the numbers;
p1: 42792903162038876741793833201
p2: 5251334500248543640310644653
q1: 48108587971617461248207
q2: 7879795162021658598594
d0: 356655217120480268
the following is the excerpted dialogue;
Factor p: 2247198487406097477067836052277719957608999017369887
20761
Factor q: 379085818750444629059904329632899292667120189
Product Number: 8518810784931011955874437838237260204237939707
6643617313911966832546677419884547207483944896946543829
Public Key: 356655217120480269
Private Key: 4408567556048741142507080873744207288832183611289
1103321710629250645857752903220385520269143947038309
the generation of which required 4 hr 17 min 59 sec.
Further examples may be found in the text files named DIALOG6,
DIALOG7, DIALOG8, and DIALOG9 with performance summarized below.
RSA Crypt and Clear Application
===============================
The programs RSACrypt and RSAClear use the public product
number and the public and private keys, respectively, to encrypt
and decrypt specified files. This release makes no provision for
piping the control information or for redirecting the text via
the console.
The following text is found in TEXT1;
"We the People of the United States, in order to form a more
perfect Union, establish Justice, insure domestic Tranquility,
provide for the common defence, promote the general Welfare, and
secure the Blessings of Liberty to ourselves and our Posterity,
do ordain and establish this Constitution for the United States
of America."
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
The Preamble is not something ordinarily kept secret but is
a readily recognized text.
EXAMPLE 1
TEXT1 is encrypted with the following dialogue;
A>rsacrypt
Product Number: 50880456227911033573
Public Key: 90859
Infile: b:text1
Outfile: b:crypt1
****************************************************
where each * denotes a 'block' encryption. The file CRYPT1 is
produced in 2 min 46 sec.
The following console history;
A>rsaclear
Product Number: 50880456227911033573
Private Key: 31150762526139197039
Infile: b:crypt1
Outfile: b:clear1
****************************************************
decrypts CRYPT1 to form CLEAR1 which faithfully reproduces TEXT1
in 10 min 28 sec.
EXAMPLE 2
Similar transactions for the product number and keys of
Example 2 require 29 sec for encryption and 28 min 8 sec for
decryption, using the following dialogues, respectively;
Product Number: 1430125002746934077975498693071050539179
Public Key: 3
Infile: b:text1
Outfile: b:crypt1
*************************
Product Number: 1430125002746934077975498693071050539179
Private Key: 953416668497955602979970420575718132107
Infile: b:crypt1
Outfile: b:clear1
*************************
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
More complete dialogs for Examples 2, 4, and 5 are presented
in the files DIALOG2, and DIALOG4 through DIALOG9.
EXAMPLE 7
This example illustrates a problem that arises for longer
numbers when using TURBO. TURBO buffers input in a 128 byte
buffer and appends a final EOF character so that no more that 127
characters are input from a line with any tail discarded. There
fore, RSAClear and RSACrypt assume that any input of 127 char
acters means that more characters follow on the next line. If
exactly 127 characters are in the string then the following line
must be empty. For example, the files PUBLIC7 and PRIVATE7
contain the information to drive encryption and decryption for
TEXT1:
PUBLIC7
37266444656900288331155096688059111088627101584412222957281536519
10705768627710571238386389970072776413797381450882656552867163
2661608445849
41986347613815503065767490894544965
b:text1
b:crypt1
PRIVATE7
37266444656900288331155096688059111088627101584412222957281536519
10705768627710571238386389970072776413797381450882656552867163
2661608445849
12721034485902176169222785206366066259112317172652383448382414610
15278962407771023297005604627516785980553490605912044151221405
0787452026457
b:crypt1
b:clear1
Product number folding at ...36519 and private key at
...14610 are artifacts of text justification limits. The product
number break at ...67163 and the private key at ...21405 are end
of lines after 127 characters with their respective tails on
following lines. Note that the TURBO Version 2 editor folds
lines after 125 characters so that it is not compatible with the
the read process scissoring after 127 characters.
DIALOG8, along with PUBLIC8 and PRIVATE8 present another
example.
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
PERFORMANCE
The table below summarizes the run time measurements for
these examples. The numbers in parentheses show the correspond
ing RSA routine version. For these measurements the file TEXT1
was used.
example SetUp Crypt Clear
------- ----- ----- -----
# 1 3m 41s 2m 46s 10m 28s
(~20 digits) (1.2a) (1.1a) (1.1c)
# 2 12m 56s 29s 28m 08s
(~40 digits) (1.2a) (1.1a) (1.1c)
# 3 42m 08s 1m 59s 1h 05m 36s
(~60 digits) (1.1) (1.1) (1.1)
# 4 2h 11m 32s 9m 25s 1h 48m 52s
(~80 digits) (1.1) (1.1) (1.1)
# 5 4h 17m 59s 28m 27s 2h 48m 45s
(~100 digits) (1.1) (1.1a) (1.1c)
# 6 5h 05m 57s 54m 41s 3h 25m 28s
(~120 digits) (1.2a) (1.1a) (1.1d)
# 7 11h 11m 00s 1h 07m 49s 4h 50m 15s
(~140 digits) (1.2a) (1.1a) (1.1d)
# 8 27h 45m 46s 1h 30m 28s 6h 00m 38s
(~160 digits) (1.2a) (1.1a) (1.1d)
# 9 17h 28m 42s 1h 15m 02s 5h 01m 34s
(~180 digits) (1.2b) (1.1b) (1.1e)
CHALLENGE
Cryptographic writeups seem to include a test. This test is
different. Apply the following product number and public key to
the file CRYPT2 to produce CLEAR2. This text has been encrypted
by the author using the corresponding private key. This is what
is meant by a signed message. If the author had your public keys
then he could have further encrypted this message using them and
sent the result to you. You would decrypt using your private
key, and then authenticate the sender by applying his public keys
in a decryption.
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Product Number:
162517290174883004568112175886923592338804341174003220375359
Public Key:
31
It required 24 min 43 seconds to sign TEXT2 into CRYPT2. It
will require less than 51 sec to unsign the message and, in this
case produce the clear text.
COMMENT
i. The security, if any, of this scheme is in p and q,
not their product n. For example, suppose we take the
reciprocal of d mod n for the numbers of Example 2;
Product Number: 1430125002746934077975498693071050539179
Public Key: 3
Reciprocal: 953416668497956051983665795380700359453
Note that this is not the private key because the
reciprocal is formed modulo the public product number n -
not the private n'. At first sight it is startling that
this looks so much like the 'secret' factor d';
Private Key: 953416668497955602979970420575718132107
A little work will show this is unavoidable since,
necessarily, p*q >> p+q ;
d' = [2*(p-1)*(q-1) + 1] / 3
x = [2*p*q + 1] / 3
d' = x - 2*(p+q) / 3
Further, the convolution property of multiplication
guarantees that;
p1 * q1 = x1 + ?
p1 * q2 + p2 * q1 = x2 + ?
...
p1 * qm + ... + pm * q1 = xm + ?
...
pn * q1 = xm+n
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
where the ? denote carries and the pi, qj, and xk denote
digits of p, q, and x. The point is that a search does not
n m
need to consider 10 * 10 possibilities but only the
max(n,m)
highly constrained and astronomically smaller 10 .
To paraphrase John Von Neumann; "Anyone who considers
multiplicative congruential methods of producing ciphers
is, of course, in a state of innocence." The security of
this method relies on the competence and integrity of men
like D.H. Lehmer and Donald Knuth; the continuing work of
Rivest, Shamir and Adleman; and their mutual claim that
factoring sufficiently large numbers is tough.
ii. The TURBO Random function is used to generate test
numbers for the Probabilistic Primality Test. The author
does not have reference to any work qualifying this genera
tor and has performed limited testing using period, Chi
square, and autocorrelation measures. The file PERIOD.PAS
presents a simple routine to display one facet of Random's
performance. This routine prompts for a modulus and then
performs period detection trials. One replicate appears as
follows;
Modulus: 16383
Trial Initial Period
1 15404 2194
2 11573 2488
3 8901 14908
4 8397 4033
5 8772 21009
6 8054 20782
7 13588 36053
8 6593 30487
9 5512 28
10 13355 67955
11 9292 8689
12 9502 5931
13 3953 14215
14 8894 9447
15 7334 46484
The supraperiodic behavior with respect to both modulus
and range of integers suggests a shuffling generator of
some sort. It is not reassuring in applications like RSA
that this generator is proprietary.
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
iii. The file being encrypted is processed as eight bit
bytes so that either text or binary files may be encrypted.
The last block is Random filled so that another encryption
trial will not generally produce the same file with the
same inputs.
CP/M text files are terminated and filled with hexa
decimal '1A'. Therefore, the exact length of the text in a
file might be found by searching for encrypted patterns
corresponding to '1A1A .. 1A', 'xx1A .. 1A', etc. There
fore, any meaning of the message may not safely be trusted
to its exact length.
iv. The encrypted blocks are filed and retrieved as seven
bit bytes - the low order seven. Therefore, the high order
bit may be used for error control.
v. RSA is a block cipher. This has the advantage that
effects of error in one block are largely confined to that
block's output - assuming the keys are intact. A disadvan
tage is that block ciphers have a code book like vulnerabi
lity called substitution.
Suppose that a completed business form is encrypted.
Suppose further that the form has an important question
with only yes or no answers. Suppose by comparing known
clear and cipher text that the corresponding blocks are
deduced. It may be possible to substitute. The point is
that cryptography is but one element of security. Sub
stitution can be frustrated by authentication and seriali
zation. Authentication is as simple and fast as computing
and appending a CRC to the message before encryption and
then stripping, computing, and comparing after decryption.
vi. RSA is a convolutional cipher. Therefore, each key bit
osculates with each message bit. For example, consider
transformation of the following number using the keys of
Example 2;
d
12345678902345678903 mod n = 16334432371946908433
now, change one bit in the number to be encrypted;
d
12345678902345678902 mod n = 13129402162712613628
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
or change one bit in the number to be decrypted;
d'
16334432371946908432 mod n = 03578279340052214164
This problem and its many consequences are no differ
ent for RSA than for any other convolutional system of
cryptography. The point is the need to maintain integrity
at all stages in a channel. Recovery from error may require
search over the space of plausible error.
vii. The run time ratios between encryption and decryption
shown here a consequence of artificially small public keys.
Note that the roles of any two numbers reciprocal modulo
n' may be exchanged.
Security is not necessarily proportional to CPU time
and a small public key is largely a matter of considera
tion. Since the receiver is saddled with a disproportionate
burden in such cases it ill becomes a respondent to send
extraneous material. Note that the key composition process
assures availability of 3 as a key.
viii. The use of COMPACT and UNCMPACT available on some
bulletin boards can greatly reduce the total processing
time by compressing even small files before encryption. Use
of Richard Greenlaw's SQ and USQ may greatly dilate pro
cessing time because the prepended coding tree may increase
the effective size of messages that can reasonably be
expected in micro driven applications.
COMPACTion reduces message statistical redundancy which
improves the security of almost any crypto scheme. Consi
der the effect of COMPACTion on vulnerability to block
substitution. The 'whitening' effect of COMPACT also
frustrates detection of repeated blocks.
ix. These routines perform incomplete and, therefore, un
satisfactory operations to scrub memory of key traces. It
would seem necessary to remove and secure any disks and
cycle power to the machine assuming volatile memory.
Operation in a multiuser environment with the present
generation of micros is no more private than the 2001 pod
conference. Such considerations are only a beginning in
establishing and maintaining security for private informa
tion.
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
QUESTION
i. If authentication is not an issue, can the sender pick
any number as an encryption key d and use the receiver's
public product number to encrypt? So long as the sender
also tells the receiver the key d? Since the receiver
knows how to compute reciprocals modulo his n' he just
produces the d' and decrypts with it.
ii. If the sender picks a key d that is relatively prime
to his n' can he encrypt with it and send a signed message
to the receiver?
iii. Will a system based on three or more, rather than two
numbers work? That is, let p, q, and r represent primes
and n their product. Likewise, let p', q', and r' denote
their respective decrements and n' their product. Compute
d relatively prime to n and compute d' reciprocal to d
modulo n'?
iv. Can different public keys be safely assigned to
different correspondents or different classes of correspon
dence against the same product number? That is, can n be
published with d , d , ... , d where the d are crafted to
1 2 m
balance the respective correspondent imperatives? For
example, can verbore-a-gram senders be constrained to use d
that are large, have large set bit counts, and reciprocate
to private keys with small numbers and low set bit counts?
REFERENCE
(1) A Method for Obtaining Digital Signatures and
Public Key Cryptosystems
R.L. Rivest, A. Shamir, and L.M. Adleman
Communications of the Association for Computing Machinery
Volume 21, Number 2, February, 1978
(2) The Art of Computer Programming, Volume 2
Seminumerical Algorithms
D.E. Knuth
Addison-Wesley, 2nd Edition, 1981
(3) Public Key Cryptography
John Smith
BYTE Magazine
Volume 8, Number 1, January, 1983
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
TURBO Pascal (tm) Borland International
CP/M (tm) Digital Research
microShell (tm) New Generation Systems
{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 }
Š