Overview

This assignment is designed to create a set of programs that can be used for SS public- key cryptography. It consists of three main programs: keygen, encrypt, and decrypt. The keygen program is responsible for generating the public and private keys, while the encrypt and decrypt programs are responsible for encrypting and decrypting files, respectively, using the generated keys.

Modules and Algorithms

Random State Module (randstate.c/h)

This module provides functionality to initialize and clear a random state for generating random numbers using the Mersenne Twister algorithm. It includes the  following functions:

randstate_init(uint64_t  seed):  Initializes  a  random  state  with  a  Mersenne  Twister algorithm and uses seed as a random seed.

randstate_clear(): Clears and frees the memory used by the random state.

Number Theory Module (numtheory.c/h)

This module provides functionality for number theory operations such as finding the greatest  common divisor (GCD),  calculating the modular inverse,  and performing modular exponentiation. It includes the following functions:

gcd(mpz_t result, mpz_t a, mpz_t b): Calculates the greatest common divisor of a and b and stores the result in result.

mod_inverse(mpz_t result, mpz_t a, mpz_t mod): Calculates the modular inverse of a mod mod and stores the result in result.

pow_mod(mpz_t result, mpz_t base, mpz_t exponent, mpz_t mod): Calculates base to the power of exponent modulo mod and stores the result in result.

Schmidt-Samoa (SS) Module (ss.c/h)

This module provides the main functionality for the Schmidt-Samoa (SS) algorithm. It includes functions for generating public and private keys, encrypting and decrypting messages, and signing and verifying messages. The module relies on the Random State Module and Number Theory Module for generating random numbers and performing number theory operations. It includes the following functions:

log_base2(mpz_t n): Computes the log base 2 of an mpz_t n.

ss_make_pub(mpz_t p, mpz_t q, mpz_t n, mpz_t e, uint64_t bits, uint64_t iters): Makes an SS public key by creating random large primes p and q, their product n, and the public exponent e by finding a random number that is coprime to n and also bits long. ss_write_pub(mpz_t n, mpz_t e, mpz_t s, char username[], FILE *pbfile): Writes a public SS key to pbfile, with n, e, and s written as hexstrings.

ss_read_pub(mpz_t n, mpz_t e, mpz_t s, char username[], FILE *pbfile): Reads a public SS key from pbfile, with n, e, and s written as hexstrings.

ss_make_priv(mpz_t d, mpz_t e, mpz_t p, mpz_t q): Makes an SS private key from primes p and q, and public exponent e.

ss_write_priv(mpz_t n, mpz_t d, FILE *pvfile): Writes a private SS key to pvfile, with n and d written as hexstrings.

ss_read_priv(mpz_t n, mpz_t d, FILE *pvfile): Reads a private SS key from pvfile, with n and d written as hexstrings.

ss_encrypt(mpz_t c, mpz_t m, mpz_t e, mpz_t n):  SS encrypts a message m into cyphertext c.

The  numtheory  module  contains  algorithms  related  to  number  theory,  including primality  testing,  modular  exponentiation,  modular  inverse,  and  greatest  common divisor (GCD) calculation. These algorithms are fundamental to the SS algorithm and are used throughout the assignment.

The randstate module is responsible for generating random numbers for use in SS. It uses the Mersenne Twister algorithm to create pseudorandom numbers and the gmp library to work with arbitrary-precision integers.

The ss module contains the main SS algorithm functions, including key generation, encryption, decryption, signing, and verification. The key generation functions use the primality  testing  algorithms  from  the  numtheory  module  to  generate  large  prime numbers, which are then used to create public and private keys. The encryption and decryption functions use modular exponentiation, while the signing and verification functions use modular exponentiation and message hashing.

Overall, the assignment uses a combination of fundamental number theory algorithms and cryptographic techniques to provide secure communication between parties. The design of the assignment follows the principles of secure cryptography, including the use of strong cryptographic algorithms, key management, and secure communication channels.

Limitations and Future Improvements

The assignment has several limitations, including the lack of support for encryption and decryption of large files due to memory constraints. The assignment also does not support secure communication over a network. Future improvements to the assignment could  include  adding  support  for  large  file  encryption  and  decryption,  secure communication over a network, and improving the overall security of the implemented algorithm functions.