Applications of Number Theory

Pseudorandom Number Generators

We will mainly introduce the linear congruential method. We choose four numbers:

the modulus
multiplier
increment
seed

Then we generate a sequence of numbers with by using the congruence

Hash Functions

Definition: Hash Functions

A hash function is an algorithm that maps data of arbitrary length to data of fixed length. THe values returned by a hash functions are called hash values or hash codes.

The hash functions have very wide applications across different fields of programming. A classical example is given a large collection of records, how can we store and find a record quickly? Then we can use a hash function to calculate the location of the record based on the record’s ID.

Cryptography

The classic cryptography mainly studies the Symmetric cryptography, i.e. decryption and encryption use the same secret key to manipulate the message. This requires using a secure channel to transmit the key, and if the key is intercepted, the adversaries can easily decrypt the main message. A well-known example of symmetric cipher is the Caesar Cipher.

Kerchoff’s Principle

System should be secure even if algorithms are known, as long as key is secret.

Can we avoid using the common key? We can achieve this by using the public key cryptography. In this system, Alice first obtain Bob’s public key, then use this key to encrypt the message, then transmit encrypted message to Bob. Then Bob can use his secret key to decrypt the message. By using this approach, we greatly increase the security of the system. The most widely used public cryptosystem is the RSA Public Key Cryptosystem.

RSA Public Key Cryptosystem

Pick two large primes and . Let , then . Encryption (public key) and decryption keys (secret key) and are selected s.t.

Then we can do the encryption and decryption as the follows:

Theorem: Correctness of RSA Algorithm

Let and be two odd primes, and define . Let be relatively prime to and let be the multiplicative inverse of modulo . For each integer s.t. ,

Example

For the following parameters: Then the public key is , private key is . The encryption/decryption process is:

The parameters must be kept secret!

Tip

It is believed that determining is equivalent to factoring . Meanwhile, determining given and , appears to be at least as time-consuming as the integer factoring problem.

In practice, RSA keys are typically 1024 to 2048 bits long.

Question

Consider the RSA system, where is the modulus. Let be a key pair for the RSA. Define and compute . Will decryption using instead of still work?

We can also use RSA for digital signature:

The Discrete Logarithm

The discrete logarithm of an integer to the base is an integer s.t.

Then the discrete logarithm problem is: Given , , and , find .

El Gamal Encryption

Setup: Let be a prime, and be a generator of . The private key is an integer with . Let . THe public key for El Gamal encryption is .
Encryption: Pick a random integer from , The ciphertext consists of the pair .
Decryption:

We can also use El Gamal encryption for digital signature: