22. Cryptography: Encryption

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Srinivas Devadas

In this lecture, Professor Devadas continues with cryptography, introducing encryption methods.

License: Creative Commons BY-NC-SA

[kazisiddiqui]

Please keep putting these out. I follow your material religiously.

[aleksagordic]

symmetric key cryptography. (nice analogy with pirate ships)
40:55 - 1:05:40 RSA (hardness based on big number factorization)
later other crypto systems like the ones whose hardness is based on knapsack problem (broken)

[MathNerdGamer]

1:07:45
I don't think "Is N composite?" is the correct decision problem for integer factorization.
Since "PRIMES is in P" via AKS, we can run AKS on an integer to answer if it's composite or not. -> Run AKS, return opposite of what it says.

A correct decision problem for integer factorization would be something like:
"Given N, a, b, does N have a factor d such that a < d <= b?"
This is in NP because you can verify a factor in polynomial time (division algorithm).

We can then factor an integer in polytime using a polytime oracle that solves this decision problem -- just binary search for factors starting from an interval (1, N-1] by consulting the oracle (we can restrict our search to prime factors using AKS), then divide out by prime factors as many times as possible whenever one is found. Return N as the only factor if the first oracle call returns `No`.
This algorithm calls the oracle O(log N) times for each factor, and N has O(log N / log log N) unique factors (via a theorem of number theory), so all-in-all, this yields a polytime algorithm.

Of course, you'd need a polytime oracle for this to actually be implemented, but I'll leave constructing such a thing to the experts. :)

[aguy]

This needs a guide or hw. The lecture topics are confusing but I'm interested in the subject.

[OmarAbdelhamid--]

the sound and the video aren't not synchronized

[randyt]

shout out to the cameramen and all the different shots/angles they're recording lol.

[shymaaarafat]

I think he should've wrote the proof in a simpler way
Simply
Decrypted msg=(m^e mod N) ^d mod N =m^ed mod N =m^(1+X(p-1)(q-1)) mod N =[m* m^X(p-1)(q-1)] mod N = m (from fermat little theorem)
It is almost the same, but u kind of go straight forward here
(Note that in general m mod N=m, because in general m<N for the algorithm to work N is extremely large)

[alileevil]

Permutations are reversible. Ah yes I see 5head.

[darshnikdeep]

Believe me he is a dull Indian teacher and most Indian teachers aren't like that