How to resolve the algorithm RSA code step by step in the PicoLisp programming language
How to resolve the algorithm RSA code step by step in the PicoLisp programming language
Table of Contents
Problem Statement
Given an RSA key (n,e,d), construct a program to encrypt and decrypt plaintext messages strings. Background RSA code is used to encode secret messages. It is named after Ron Rivest, Adi Shamir, and Leonard Adleman who published it at MIT in 1977. The advantage of this type of encryption is that you can distribute the number “
n
{\displaystyle n}
” and “
e
{\displaystyle e}
” (which makes up the Public Key used for encryption) to everyone. The Private Key used for decryption “
d
{\displaystyle d}
” is kept secret, so that only the recipient can read the encrypted plaintext. The process by which this is done is that a message, for example “Hello World” is encoded as numbers (This could be encoding as ASCII or as a subset of characters
a
01 , b
02 , . . . , z
26
{\displaystyle a=01,b=02,...,z=26}
). This yields a string of numbers, generally referred to as "numerical plaintext", “
P
{\displaystyle P}
”. For example, “Hello World” encoded with a=1,...,z=26 by hundreds would yield
08051212152315181204
{\displaystyle 08051212152315181204}
. The plaintext must also be split into blocks so that the numerical plaintext is smaller than
n
{\displaystyle n}
otherwise the decryption will fail. The ciphertext,
C
{\displaystyle C}
, is then computed by taking each block of
P
{\displaystyle P}
, and computing Similarly, to decode, one computes To generate a key, one finds 2 (ideally large) primes
p
{\displaystyle p}
and
q
{\displaystyle q}
. the value “
n
{\displaystyle n}
” is simply:
n
p × q
{\displaystyle n=p\times q}
. One must then choose an “
e
{\displaystyle e}
” such that
gcd ( e , ( p − 1 ) × ( q − 1 ) )
1
{\displaystyle \gcd(e,(p-1)\times (q-1))=1}
. That is to say,
e
{\displaystyle e}
and
( p − 1 ) × ( q − 1 )
{\displaystyle (p-1)\times (q-1)}
are relatively prime to each other. The decryption value
d
{\displaystyle d}
is then found by solving The security of the code is based on the secrecy of the Private Key (decryption exponent) “
d
{\displaystyle d}
” and the difficulty in factoring “
n
{\displaystyle n}
”. Research into RSA facilitated advances in factoring and a number of factoring challenges. Keys of 829 bits have been successfully factored, and NIST now recommends 2048 bit keys going forward (see Asymmetric algorithm key lengths). Summary of the task requirements:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm RSA code step by step in the PicoLisp programming language
Source code in the picolisp programming language
### This is a copy of "lib/rsa.l" ###
# Generate long random number
(de longRand (N)
(use (R D)
(while (=0 (setq R (abs (rand)))))
(until (> R N)
(unless (=0 (setq D (abs (rand))))
(setq R (* R D)) ) )
(% R N) ) )
# X power Y modulus N
(de **Mod (X Y N)
(let M 1
(loop
(when (bit? 1 Y)
(setq M (% (* M X) N)) )
(T (=0 (setq Y (>> 1 Y)))
M )
(setq X (% (* X X) N)) ) ) )
# Probabilistic prime check
(de prime? (N)
(and
(> N 1)
(bit? 1 N)
(let (Q (dec N) K 0)
(until (bit? 1 Q)
(setq
Q (>> 1 Q)
K (inc K) ) )
(do 50
(NIL (_prim? N Q K))
T ) ) ) )
# (Knuth Vol.2, p.379)
(de _prim? (N Q K)
(use (X J Y)
(while (> 2 (setq X (longRand N))))
(setq
J 0
Y (**Mod X Q N) )
(loop
(T
(or
(and (=0 J) (= 1 Y))
(= Y (dec N)) )
T )
(T
(or
(and (> J 0) (= 1 Y))
(<= K (inc 'J)) )
NIL )
(setq Y (% (* Y Y) N)) ) ) )
# Find a prime number with `Len' digits
(de prime (Len)
(let P (longRand (** 10 (*/ Len 2 3)))
(unless (bit? 1 P)
(inc 'P) )
(until (prime? P) # P: Prime number of size 2/3 Len
(inc 'P 2) )
# R: Random number of size 1/3 Len
(let (R (longRand (** 10 (/ Len 3))) K (+ R (% (- P R) 3)))
(when (bit? 1 K)
(inc 'K 3) )
(until (prime? (setq R (inc (* K P))))
(inc 'K 6) )
R ) ) )
# Generate RSA key
(de rsaKey (N) #> (Encrypt . Decrypt)
(let (P (prime (*/ N 5 10)) Q (prime (*/ N 6 10)))
(cons
(* P Q)
(/
(inc (* 2 (dec P) (dec Q)))
3 ) ) ) )
# Encrypt a list of characters
(de encrypt (Key Lst)
(let Siz (>> 1 (size Key))
(make
(while Lst
(let N (char (pop 'Lst))
(while (> Siz (size N))
(setq N (>> -16 N))
(inc 'N (char (pop 'Lst))) )
(link (**Mod N 3 Key)) ) ) ) ) )
# Decrypt a list of numbers
(de decrypt (Keys Lst)
(mapcan
'((N)
(let Res NIL
(setq N (**Mod N (cdr Keys) (car Keys)))
(until (=0 N)
(push 'Res (char (& `(dec (** 2 16)) N)))
(setq N (>> 16 N)) )
Res ) )
Lst ) )
### End of "lib/rsa.l" ###
# Generate 100-digit keys (private . public)
: (setq Keys (rsaKey 100))
-> (14394597526321726957429995133376978449624406217727317004742182671030....
# Encrypt
: (setq CryptText
(encrypt (car Keys)
(chop "The quick brown fox jumped over the lazy dog's back") ) )
-> (72521958974980041245760752728037044798830723189142175108602418861716...
# Decrypt
: (pack (decrypt Keys CryptText))
-> "The quick brown fox jumped over the lazy dog's back"
You may also check:How to resolve the algorithm Increment a numerical string step by step in the EGL programming language
You may also check:How to resolve the algorithm Shell one-liner step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Numerical integration step by step in the ALGOL W programming language
You may also check:How to resolve the algorithm Quickselect algorithm step by step in the Maple programming language
You may also check:How to resolve the algorithm N-queens problem step by step in the Logo programming language