Rodrigo
  • Member for 5 years, 3 months
  • Last seen more than a month ago
In RSA, what is $P[x \notin \mathbb{Z}_N^*]$
Accepted answer
4 votes

With fgrieu's idea: If we consider the generator working on a security parameter of $n$ bits (meaning resistance to $\mathcal O(2^n)$ computational effort), then each of the prime $p$ and $q$ must be ...

View answer
Probability of Fermat test going wrong
Accepted answer
2 votes

I give an answer summarizing and precising the comments you provided. Being invertible in $\mathbb{Z}_{n }$ is equivalent to having some power equal to 1. If $b$ is invertible there exist $b^{-1}$ ...

View answer
Given a PRF $F$ , is $G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$ a PRG?
1 votes

Consider the following game: I assume certain familiarity with the definitions of Katz and Lindell book (this is exercise 3.14 in the book). In particular, $O$ is denoting an oracle. It can be either ...

View answer
Why constrain the message lengths in indistinguishability in the presence of an eavesdropper?
1 votes

The solution proposed in Katz and Lindell for this goes along these lines. Let $q(n)$ be a polynomial upper-bound on the length of the ciphertext when $\Pi$ is used to encrypt a single bit, i.e., if ...

View answer
Elliptic curves in Edwards form (or Edwards curve) and addition formulas
0 votes

Hales proposed and verified a proof for the group law of elliptic curves in Edwards form. It does not use sophisticated tools. I'm currently porting his proof fully into a proof assistant.

View answer
Padding schemes reversal and space efficiency
Accepted answer
0 votes

The more space efficient but cannot always be reverted, for instance if one inputs $m = 1$. The second space efficient but can always be reverted, this appears in Wikipedia entry as bit padding. and ...

View answer
Breaking ElGammal encryption of two different mesagges
Accepted answer
0 votes

Thanks to poncho's hints we can work as follows: 1.Compute $(g^r)^q$. I claim that: $ (g^r)^q = \begin{cases} 1 &\quad\text{if r is even}\\ \neq 1 &\quad\text{if r is odd}...

View answer