When I learned to program, I was always annoyed with solving uninteresting tasks in practice. Now I teach, and I don’t want students to miss my classes.

In this article I solve in MIT Scheme the problem of encryption and decryption using the RSA method [1]. For several reasons, which are discussed in the article, the implementation cannot be used for cryptographic protection of information.

Key generation - search for prime numbers

RSA refers to asymmetric encryption algorithms: if a public key is used for encryption, the private key is used for decryption, and vice versa. The first property allows anyone to encrypt a message with a public key to the owner of the private key and thereby ensure its confidentiality. The second property allows the key owner to encrypt the message hash with the private key so that anyone can decrypt the encrypted hash, compare it with the message hash, and determine if the message has been modified.

The first step in key generation is a random selection of two sufficiently large primes p and q. A natural number x is called simple if it has exactly two different divisors: 1 and x. All other divisors of the number are located on the segment from 2 to the square root of x; however, it suffices to check for multiplicity only the prime divisors belonging to this segment.
')

  (define (Primes n)
   (define (prime? n primes)
     (define (iter divisors)
       (or (null? divisors)
           (let ([divisor (car divisors)])
                (or (> (* divisor divisor) n)
                    (and (<0 (remainder n (car divisors))) (iter (cdr divisors))))))
       )
     (iter primes)
     )
   (define (iter primes i candidate)
     (cond 
       ((= in) primes)
       ((prime? candidate (reverse primes)) (iter (cons candidate primes) (+ i 1) (+ candidate 1)))
       (else (iter primes i (+ candidate 1)))
       )
     )
   (iter '() 0 2)
   )
 (define primes (Primes 100))
 (define p (car primes))
 (define q (car (drop 10 primes))) 

The product of the found primes is the first element of the public and private keys. The above algorithm allows you to find in a reasonable time only the first million prime numbers. In RSA implementations used to protect information, algorithms for searching for primes are used, which allow finding primes with a greater number of digits; due to the fact that the best known algorithm for decomposing a number into prime factors works in a time proportional to the exponent of the number of digits, it is considered that it is impossible to recover a pair of prime numbers by the considered element of the public key [2].

  (define n (* pq)) 

Key generation - search for a mutually simple number

To calculate the second elements of the public and private keys, the value of fi equal to the Euler function [3] calculated on n is used. The Euler function of x is equal to the number of positive integers not greater than x and relatively prime to it. For n, this number will be equal to the product of p-1 and q-1.

  (define fi (* (- p 1) (- q 1))) 

The second element of the public key is chosen random number e in the range from 1 to fi, which is mutually simple with fi. that is, such that the greatest common divisor of numbers is 1.

  (define (CoprimesLess n)
   (define (iter accumulator candidate)
     (cond
       ((= 1 candidate) accumulator)
       ((= 1 (gcd n candidate)) (iter (cons candidate accumulator) (- candidate 1)))
       (else (iter accumulator (- candidate 1)))
       )
     )
   (iter '() (- n 1))
   )
 (define e (car (drop 5 (CoprimesLess fi))))) 

To find the greatest common divisor, you can use the Euclidean algorithm [4].

Key generation - operations in the ring

One of the objects studied by number theory is the residue ring [5]. The residue ring modulo k is integers from 0 to k-1 and the operations of addition and multiplication on it. Addition in the residue ring (a + b mod k) differs from addition in the group of integers in that if the result of the addition becomes greater than k, k is subtracted from it, with the result that this result is again in the ring. Intuitively, a ring is obtained from a segment by connecting its ends.

As in the group of integers, multiplication in a residue ring can be specified by addition, and exponentiation can be specified by multiplication. As in the group of integers, the resulting operations of addition and multiplication will have associativity, that is:
a + (b + c mod k) mod k = (a + b mod k) + c mod k
a * (b * c mod k) mod k = (a * b mod k) * c mod k

The second element of the public key must be the number d such that its product with e in the residue ring modulo n is 1, that is, multiplicatively the inverse element. I cite an algorithm for finding such an element using the advanced Euclidean algorithm [6].

  (define (MultInverseModN an)
   (define (iter a-prev a r-prev r)
     (if (> = 1 r) a (let * ([r-next (remainder r-prev r)]
                           [q (quotient r-prev r)]
                           [a-next (- a-prev (* qa))])
                          (iter a a-next r r-next)))
     )
   (let ([result (iter 0 1 na)]) (if (<0 result) result (+ n result)))
 )
 (define d (MultInverseModN e fi)) 

Encryption and decryption

Using the RSA algorithm, you can encrypt messages represented by a series of M numbers in the range from 0 to n-1. Encryption consists of raising M to degree e in a residue ring modulo n, deciphering to degree d. Due to the fact that multiplication is associative, we can raise to the power of x for log (x) operations [7].

  (define (PowerModN abn)
   (define (iter accumulator multiplicator power)
     (if
       (= power 0)
       accumulator
       (let
           ((new_accumulator (if (even? power) accumulator (remainder (* accumulator multiplicator) n))))
           (iter new_accumulator (* multiplicator multiplicator) (quotient power 2))
         )
       )
     )
   (iter 1 ab)
   ) 

Test case

In my example, the public key is a pair (250483 31), the private key is a pair (250483 32191). The encrypted message 123456 is equal to 133240.

Links

1. en.wikipedia.org/wiki/RSA
2. en.wikipedia.org/wiki/Integer_factorization
3. en.wikipedia.org/wiki/Euler%27s_totient_function
4. en.wikipedia.org/wiki/Euclidean_algorithm
5. en.wikipedia.org/wiki/Modular_arithmetic
6. en.wikipedia.org/wiki/Extended_Euclidean_algorithm
7. en.wikipedia.org/wiki/Exponentiation_by_squaring