New answers tagged


There's been some interesting research published since @imichaelmiers's answer. It looks like asynchronous messaging / 0-RTT / store-and-forward isn't quite as incompatible with practical perfect forward secrecy as was once thought! Green & Miers, 2015, 'Forward Secure Asynchronous Messaging from Puncturable Encryption' provides a couple of primitives ...


Since $\gcd(2,467)=1$, one can observe using Fermat's little theorem that $4^{233}\pmod{467}=2^{466}\pmod{467}=1$. Thus, $$g^{a_1}=4^{400}=4^{233+167}\equiv\underbrace{1\cdot4^{167}}_{=g^{a_2}}\pmod{467}=89.$$ This results into identical session keys (shared secrets) $S=(g^a)^b=89^{134}\equiv161\pmod{467}$.


One concrete solution is to explicitly compute the distribution of each coefficients. In this particular ring, and if the distribution of the coefficients of e and s are symmetric, this ca just be computed as an 2n-fold convolution of the distribution of products of coefficients. An example (with some complication due to rounding) is available here: https://...


Are there any other issues, besides the randomness of the 256-bit private key to consider? Not really. The DLog problem really doesn't have any 'weak keys', that is, keys that can be broken with less effort than other keys. Now, you might say "hey, isn't the key '1' easier to break than others?" Not really; you might consider '1' easy to break because $g^...


There is a condition that is not considered, that is, the value after modulo 257 should be in $\mathbb Z_q$. When $q = 257, \mathbb Z_q = \{ -128, ... , 128 \}$, so, $(4+128)\mod 257$ should be $-125$ rather than $132$ . And $-125 \mod 2 = 1$. Thus, $sk_a \neq sk_b$ and the output of oracle $\mathcal B$ is $0$.

Top 50 recent answers are included