New answers tagged modular-arithmetic
3
There are two reasons for not using $\varphi(n)$ during encryption.
The first one is that it doesn't work - you can verify this by looking at the RSA correctness proof. It requires, that the modulus is $n$.
The second one is - if you know $\varphi(n)$ you can efficiently compute $d$ given $e$, and therefore know the private key.
0
Elliptic curves confuse many in the beginning because of its construction. The elliptic curve can be defined in any field, however, in cryptography, we are interested in curves over finite fields. This can be a prime field $\Bbb F_p$, or an extension field $\Bbb F_q$, where $q=p^m$ for some positive integer $m$. The prime can be 2 that we called a binary ...
0
All field operations are modulo prime modulus and it means they must be smaller than modulus but can be $\ge$ order?
Yes, in theory that could happen, but it is rare. All quantities manipulated in the field usually are about uniformly random in $[0,p)$ when reduced modulo $p$. Therefore they seldom exceed $n$. The probability is about $1-n/p\approx2^{-127....
2
Yes, field operations may involve numbers that are larger than the order. Public key point coordinates may exceed the order.
Parts of the protocol that handle scalars work modulo the curve order, while the parts that handle elliptic curve points work modulo the prime modulus.
Sometimes, as you noted, some information "crosses" between these domains:...
2
Moderator note: This answers a different question that I incorrectly merged:
Consider a number $r$ obtained by:
$\quad r=a⋅b\bmod n$
Can knowing the factorization of $r$ reveal some information (bits) of $a$ and $b$ ?
The factoring of $r$ is not unique $\pmod n$.
0
Is there any way to solve for pair(x,y)?
If you're looking for an arbitrary pair, it's easy (assuming $a \ne 0$).
Pick an arbitrary $y$
Solve for $f(x) = y^3$; that'd be $x = a^{-1}(y^3 - b) \pmod{n}$
You're done.
Top 50 recent answers are included
