csp 9a chapter 4 - public key cryptography

what do messages on computers travel through?

numerous routers

addition trick

message is encrypted by adding it to a shared secret number that only the other recipient knows

how many digits are in the key of 128-bit encryption

30% of 128 = 38 digits

block cipher

break up long messages into blocks of fixed size, each block is transformed several times through different fixed operations, resulting in a truly mixed up original msg that can only be reversed by someone w/ the key

advanced encryption standard

• most popular block cipher

• typically uses blocks of 16 characters w/ 128-bit keys and 10 rounds of mixing operations

1st step of paint-mixing trick

you and arnold choose a private color

• ex: lavender and crimson

2nd step of paint-mixing trick

publicly announce ingredients of new, public color

• ex: daisy yellow

3rd step of paint-mixing trick

combine one pot of public color w/ pot of private color → public-private mixture

4th step of paint-mixing trick

take a batch of other person’s public-private mixture and add a pot of your private color

one-way action

something that can be done but not undone (like paint mixing)

• in book, assume multiplication is one-way

steps of paint-mixing using #’s

1) choose private numbers

• ex: 4 and 6

2) announce public number

• ex: 7

3) multiply priv # by public to get public-private

• 4×7=28 and 6×7=42

4) multiply public-private number by your private number

• 42×4=168

discrete exponentiation

mixing paint operation (oneway action)

discrete logarithm

un-mixing paint operation

clock arithmetic

arithmetic works like a clock (limited to a certain amount of numbers that reset) but

• clock can be any number size

• numbers start at 0 and not 1

arithmetic is done as normal, but answer only counts remainder after dividing by clock size

power notation

6×6×6 = 6³

using discrete exponentiation steps

1) each person chooses a private number (8 and 9)

2) agree on two public numbers: a block size (11) and base (2)

3) create public-private number (PPN) using

• PPN+base^private # (clock size)

• ex: 2^8 = 3 (clock size 11) & 2^9=6 (clock size 11)

4) take each others PPN and mix w/ your private #

• shared secret = other PPN^private # (clock size)

• ex: shared secret = 6^8 = 4 (clock size 11)

diffie-hellman key exchange protocol

named for whitfield diffie and martin hellman who published the algorithm in 1976 (paint mixing w/ powers and clock arithmetic)

most important property for diffie-hellman public numbers?

clock size must be a prime number, base must be a primitive root of clock size (powers cycle through every possible value on clock)

what is diffie-hellman approach known as to computer scientists?

key exchange algorithm

most famous public key cryptosystem

RSA - rivest, shamir, adleman