Midterm 1 Cryptography

Euclid’s Propostion

if p|a•b then p|a or p|b

Proof of Infinite Primes

BLANK

Principle Modulo

Smallest pos int b in

a = b mod n

2 Methods to Verify Congruency

1. Find principal modulo of both

2. does n|a-b

The Order of an Element exists Proof

BLANK

Fermat’s Little Thm

if gcd(a,p) = 1 then

a^(p-1) = 1 mod p

Order of the Multiplicative Group?

It’s the Euler Phi Function

so U(6) = phi(6) = 2

How to Use the Euler Phi Function

gcd(n,m) = 1 then phi(nm)=phi(n)phi(m)

if phi(p^n) then phi(p^n) = p^n - p^(n-1)

phi(p) = p-1

RSA n

n=pq

RSA e

e is between 1 and phi(n)

e is relatively prime to phi(n)

RSA d

ed = 1 mod phi(n)

RSA encrypt message m

m^e mod (n)

RSA Decrypt m

m^d mod n

RSA what is public

n,e

How many Generators of U(p)

phi(p-1)

Primitive Root also means

generator

given Zp*, possible orders of elements?

1,2,p-1/2,p-1

Is y a square?

To find the potential square roots take

x^(p+1/4) mod p

the check if x squared gives y

if it doesn’t then -y is the square instead

possible orders of elements in general?

i think the order of elements must divide the order of the group

How to convert letters to numbers?

A is 1 B is 2…

then take message starting from RightSide

Ex: m: AC B

B*27^0 + SPACEIS0×27^1 + C*27² + A*27³

Convert Numbers to Letters?

Take big number and divide by base

123/27 the rem is the letter

then to continue next line would be 4/27 with rem 4

(i got 4 bc 123/27 is 4)

then message is from btm up. so the letter you get last is the first in the message

Diffie Hellman Shared Key

p, g are public

g is a generator, p is prime

A= g^a (mod p)

B=g^b (mod p)

Key=B^a (mod p) + A^b (mod p)

Miller Rabin Test

a^(n-1) mod n

you are testing n

do a couple values of a

if it’s always 1 then n is likely prime

El Gamal Public Key System

p, g, B is public

B = g^a mod p

r=g^k (mod p)

t=B^k • m

(r,t) is sent

Decide El Gamal

t•(rInverse)^a = m (mod p)

Close Primes RSA

take sqrt(n)

set t=sqrt(n) + 1

keep increasing t until sqrt(t² -n) is perfect square

then p = t + sqrt(t² - n)

and use calc for q