# Tag Info

0

As pointed out in the comments by poncho m only depends on the lower i+1 bits of n . Therefore n can be reconstructed by testing the four possible states of the the two most significant bits at a time, starting with the first ones, then choosing the combination that produces the correct binary suffix to expand iteratively.

0

We can write $m$ as $$m = (c -3 + 4k) \cdot 5^{-1} \pmod n$$ There is a problem here that the 5 may not has an inverse for every $n$. For example, it doesn't have an inverse in $\mathbb{Z}_{10}$. It has an inverse in $\mathbb{Z}_{n}$ if $\gcd(5,n) =1$. If it has the inverse one can find it by the Extended Euclidean Algorithm to form the Bézout's ...

0

The standard RSA ($c=m^{e}$ $mod(n)$) is not semantically secure, since it reveals one bit information about the message. This information is jacobi symbol of the message. You can find many resources about jacobi symbol but basically it states that a value is in $QR_n$ or not. In CL signature, we can handle with this situation easilly, since we determine the ...

3

Remark: $p$ and $q$ are distinct odd primes (if not, we can factor $N$), thus $\phi(N)=(p-1)(q-1)$. Define $p'=(p-1)/2$ and $q'=(q-1)/2$. It holds $\phi(N)=4\,p'\,q'$. What's asked is not always possible. As a counterexample, assume $k=2$ (which is a possible $k$, from above remark), and $p\equiv 3\equiv q\pmod4$ (which covers about 25% of RSA keys). If we ...

2

Disclaimer: I'm not familiar with NTRU, and not in my comfort zon. Hence the many edits. The problem asked can be summarized as: given $n$, $q$ coprime to prime $p$, and for $0\le i<n$ the coefficients $f_i\in\{-1,0,1\}$ of $F=\displaystyle\sum_{0\le i<n}f_i$, find the $n$ coefficients $q_i$ of $F_q$ and $p_i$ of $F_p$ such that, with polynomial ...

Top 50 recent answers are included