December 07, 2005

Reading up on 'mere steganography' by Bruce Schneier. Guess who employs the most mathematicians in the world?* What is the memorandum of understanding between the director of the national institute of standards and the director of the national security agency?** What is zero-knowledge proof of identity and why did the us army force the us patent office to deny issuing a patent on the algorithm on the grounds that it would compromise national security?***

I love the oiler phi function. Sometimes called the euler totient function. Is that supposed to rhyme with quotient? If n is a prime number, phi(n) = n - 1, which is the count of integers below n and greater than 0 that are not a multiple of n.

The n - 1 part comes from the fact that a prime number has no factors less than n.

1 is better known as 0 in this world where there is a limit to the maximum number you can 'use'. like on a clock, you can only use up to 12 then it goes back to 1. where is zero again? sometimes this set of numbers from 1 to n is called a finite field, or a galois field. in such a field, you use clock arithmetic.

so if n were 7 and since 7 is prime, phi(7) = 7 - 1 = 6.

cryptographers can do some mere steganography with primes and the phi function and also fermat's little theorem, which oiler later generalized. it defines what 1 means in a finite field.

let s = phi(n) and let n be prime.
then s = n - 1.

x^s = 1 mod n

x to the s power is equal to one, mod n (mod n means the max number you can use. it's also called the remainder function. 5 mod 3 is 2--the remainder when of 5 divided by 3. 6 mod 3 is 0--there is no remainder when you divide 6 by 3, it goes in evenly.)

it's kind of astonishing that if you take some astronomical prime n like 982347592873458907234058972340958723945790234871 (probably not prime), then subtract one from it, raise a number x to the n-1 power and have it come out to be 1.

perhaps not, it's just a clock.

public-key cryptography is all about 2-way functions. really a one function and it's inverse.
invertible. we can use the phi function again to help us with calculating inverses.

intutively you know what this is: in addition, it's any number added to another number to give zero. the inverse of 4 is -4. in multiplication, it's any number times another number to give one. the inverse of 4 is 1/4 since 4 * 1/4 = 1.

so say we have a huge prime number x. how do we find it's inverse in a prime finite field?

it's you remember a few tricks about exponents, it's not that difficult. in simple text like this, ^ means raise to the power. when you multiply x^2 * x^3 = x^(2+3) = x^5 because the trick is to add exponents.

the inverse of x is defined as x to the minus 1, x^(-1)

so the question is what do i multiply x by to get 1?
x^(-1) of course since:

x * x^(-1) = x^1 * x^(-1) = x^(1 + -1) = x^0 = 1

now we can do a little trick with phi(n) = n - 1.

let s = n - 1 again.

x * x^(s-1) = x^1 * x(s-1) = x^(s+1-1) = x^s

now from oiler's generalization of fermat's little theorem
we know:

x^s = 1 mod n

so the inverse of x, x^(-1), must be x^(s-1)
since we mulplied it by x and the answer was 1.
that's the definition of an inverse.

i gotta build the fucking . . .
i gotta merge the fucked up . . .
i gotta archive the god damn . . .

later
bill


-----------------
*NSA
**Listen to me. Ok.
***Feige-Fiat-Shamir

Blog Archive