FFT/RSA/Acronyms R Us

Notes on Homework....

The Fast Fourier Transform, in brief

Private-Key Cryptosystems

Public-Key Cryptosystems

Groups!

The RSA Encryption System

Your Pain, Again....

July 24: Homework not due because of typo; FFT; RSA; Homework goes out

July 31: Homeworks due; NP-completeness; Final goes out

August 7: Final due; Voronoi fun!

The Discrete Fourier Transform

Given , and using , the (discrete) Fourier transform is

The degree is , or is a series of samples

This is where MP3 audio comes in
PCM audio (CD audio) is a series of amplitude samples
Discrete Fourier transform produced
Low Fourier transform coefficients are dropped (compression)

Fast Fourier Transform

fft [a] = a

fft l@(a:rest) =

let n = length l

omega = e**(2*pi*i/n)

evens = everyother l

odds = everyother rest

evenfft = fft evens

oddfft = fft odds

y m = evenfft !! m + omega * oddfft !! m

z m = evenfft !! m - omega * oddfft !! m

in

concat

(map y [0..n/2])

(map z [0..n/2])

Private-Key Cryptosystems

Aaron and Betty want to communicate a message M

A and B share function s and transmit s(M) rather than M

In general, s is difficult to invert but....

If s is discovered, all messages are compromised
If discovery of s is undetected, then spoofing can occur
Some s's are easier to invert than others; Permutations are notoriously easy (rot13, duh)

Function s often known, but requires a special value, a key

Currying fun!

mycrypt message = encrypt key message

mycrypt = encrypt key

Public-Key Cryptosystems

A and B each have a pair of keys/functions, Secret and Public, s.t.

A encodes with then ; B decodes with then

Or, in Code

A writes to B, or decodes from B:

module A (Apublic) where

import B

codeForB message = Bpublic Asecret message

And vice versa, B to A:

module B (Bpublic) where

import A

codeForA message = Apublic Bsecret message

If A decodes from B, A knows B sent it and B knows only A can read it (and vice versa)

Signature is simply encoding using private key; decode with public key confirms author

Whence RSA?

Approach of public key system due to Diffie and Hellman

"Wouldn't it be nice if we could find functions such that...."?

Rivest, Shamir, and Adleman proposed the RSA cryptosystem

Yes, it is the same Rivest as in "CLRS"
First widely used public key system

Why is RSA cryptographically strong?

Encoding is multiplication of relatively prime numbers
Decoding becomes factorization, i.e., time-consuming

Groups!

Why did we care about groups on the midterm?

RSA is not simply multiplication, but multiplication mod some other number

Multiplicative group mod n is key to RSA

Given multiplication mod n, choose the set

E.g., ; size denoted by

The RSA Encryption System

Choose two large primes, and ; let

As it happens,

Choose , small, odd, and relatively prime to

Compute , the multiplicative inverse of under

Public key is ; secret key is

Encryption of M is ; decryption is

RSA in Code

encode n e msg = mod (msg^e) n

 

toAfromB n b a msg =

let rsa = encode n in

rsa b (rsa a msg)

And in use....

let p = 17

q = 19

n = p * q

phi = (p-1) * (q-1) -- 16 * 18 = 288

e = 23

d = 263 in

encode n e msg

Efficient Modular Powers

Mod "inside" or "outside"

-- O(n), but bounded by n

encode' n 0 msg = 1

encode' n 1 msg = mod msg n

encode' n e msg = mod ((mod (msg * msg) n) *

(encode' n (e-1) msg)) n

Log-n

encode'' n 0 msg = 1

encode'' n 1 msg = mod msg n

encode'' n e msg =

let bits = bitsrep e

modexp a n d b' =

if d then mod (d * d * a) n

else mod (d * d) n

in foldr1 (modexp msg n 1) bitsrep

Reading for next week

CLRS 34: NP-Completeness