Skip to content

Latest commit

 

History

History
43 lines (33 loc) · 3.19 KB

specifications.md

File metadata and controls

43 lines (33 loc) · 3.19 KB

Specifications

  • RSA implementation done in Rust.
  • All the needed prime number generations will be implemented by me, as well as the relevant key generations.
  • The primes will be generated by running a randomly generated number first through low level primality test and then checking with the Miller Rabin primality test if the number is prime.
  • D calculated using the extended Euclidean algorithm
  • Also actual text encryption will be possible
  • The final program will only take text as an input and return the RSA encypted text, UTF-8
  • Time complexity still unclear
  • I am a TKT student
  • The whole project will be done in english
  • A chat mode is a possibility

Functionality

  • Generate a key pair
  • Encrypt a message with user supplied keys, or with generated keys
  • Decrypt a message with user supplied keys
  • Demo mode
  • Demo mode with user supplied message

Key generation

The required primes, p and q are generated by the following method: first, a candidate is chosen at random. Then the candidate is ran through a list of small primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31], and the divisibility is checked. If the remainder is zero, the candidate is discarded and a new candidate is chosen. If the candidate passes it is then ran through the Miller-Rabin primality test, the number of iterations is 50, so if the candidate passes, the probability is very high that the candidate is a prime. This is done for both p and q. n is simply p $\times$ q. e is 65537 since it is a Fermat prime. Now $\phi$ is just $p - 1 \times q - 1$. Next the program checks if e and $\phi$ are coprime. Panic if they are not. Then d is calculated using the extended Euclidean algorithm. Because calculating d with the EEA can result in d being negative, test if it is, and if it is negative, add $\phi$ to it, to make it positive. Now we have the public key (n,e) and private key(n,d).

Encryption

Encryption is done by converting the UTF-8 string into an integer, by converting the characters into integers = m. Then using the public key we compute the ciphertext c by raising the plaintext message to the power of e modulo n $c = (m^e mod(n))$. Now we have an integer, which is c, plaintext converted into an integer an then encrypted with the public key.

Decryption

First the encrypted integer is calculated back into the plaintext integer by $m = (c^d)mod(n)$. Then the reverse of the abovementioned is applied, converting the integer back to UTF-8, and now we have the plaintext message.

References