## Sunday, November 19, 2017

### Cryptography course notes

https://www.coursera.org/learn/crypto

Stream Ciphers 4 - What is a secure cipher?

Statistical tests - given an input it will tell how random it is.
Advantage - |Pr(A(PRG) = 1) - Pr(A(R) = 1)| A is statistical test which will return 1 if it thinks input is random enough. Advantage is close to 1 if A can distinguish very well between a truly random number and PRG random number else it's close to 0.

A PRG is secure if ADV_PRG[A,G] is negligible. It means it's difficult to distinguish between PRG and truly random.
Are there provably secure PRGs? We don't know. It's linked to P = NP.

Secure PRGs are unpredictable. Given first i bits if an algo can predict the i+1 bit with prob > 1/2 + epsilon where epsilon is non-neg then PRGs is predictable and Advantage > epsilon.
Theorem => if for all i in (0 to n-1) PRG G is unpredictable at position i then G is secure PRG.
If next bit predictors can't distinguish G from random then no statistical test can.

Semantic Security - if attacker can't distinguish between Exp(0) and Exp(1) - i.e. m0 and m1. Definition similar to advantage.

Quiz
<?php
\$cipherText = '6c73d5240a948c86981bc294814d';
\$originalText = 'attack at dawn';
\$newText = 'attack at dusk';
\$otpInAscii = pack('H*',\$cipherText) ^ \$originalText;
\$newCipherText = bin2hex(\$otpInAscii ^ \$newText);
echo \$newCipherText;
?>

Stream cipher with scure PRG is semantically secure -