Hot answers tagged

7

TL;DR: it is a matter of conventions and context that $e=1$ is allowed or not. Definitions of RSA vary: The original RSA article asks to first choose the private exponent $d$ as « a large, random integer which is relatively prime to $(p−1)\cdot(q−1)$ », then to compute $e$ as « the “multiplicative inverse” of $d$, modulo $(p−1)\cdot(q−1)$ ». This makes it ...


5

Well, it's good that you're trying to learn. However, learning from the original seminal papers does have some issues that you need to be aware of. For one, sometimes the original authors did not anticipate some issues that later contributions found (and for which common practice adjusted for). For example, it is now recognized that public key encryption ...


5

Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest, including with a modulus much too large to be factored. I'll assume unknown $n=p\,q$ with $p$ and $q$ unknown distinct large primes of comparable order of magnitude, say $\max(p,q)<...


5

In the normal setting $n=pq$ is public knowledge and $\varphi(n)$ is hidden, for a start. I will assume $$ed\equiv 1 \pmod {\varphi(n)}\quad(1).$$ Since $$\varphi{(n)} = (p - 1)(q - 1) = pq - p - q + 1 = (n + 1) - (p + q)$$ Also, $n = pq$ and some manipulation gives $$n = p \left ( n + 1 - \varphi{(n)} - p \right ) = -p^2 + (n + 1 - \varphi{(n)})p$$ and then ...


4

It is possible that find the a, b, c randomly in here? $abc \equiv 1{\pmod {\varphi (N)}} $ The most obvious way is to select $a, b$ randomly (relatively prime to $\phi(N)$), and then compute $c = (ab)^{-1} \bmod{ \phi(N) }$. It is easy to show that if $a, b$ are chosen uniformly and independently from $\mathbb{Z}_{N}^*$, then $c$ is also chosen uniformly....


4

Am I correct in assuming that it is not wrong to impose the condition that a transformation must at least be invertible in order to be considered encryption? Yes, strictly speaking: Encryption is the process of turning a plaintext message into a ciphertext (encryption) which then can later be turned back into the original plaintext (decryption). If I am ...


2

Is this true? I'd generalize it, and replace $(p-1)(q-1)$ with $X$; that is, if $X-1$ is divisible by $e$, that is, if $X-1 = k \times e$ for some integer $k$, then $\gcd(e, X) = 1$. Is this true? If it is, then your original statement is also true (because if it holds for all $X, e$, it also holds for all $X$ that is of the form $(p-1)(q-1)$ and for all ...


2

If is not possible to reversibly compress a 64-bit RSA key (nor a 64-bit prime) into 10 digits after the fact: there are just too many such keys or primes to assign them a unique 10-digit value. And at this size RSA is totally insecure, I mean breakable in a fraction of a second. Even 640-bit is insecure, see history or factorization records there. However, ...


2

The comment by @Krystian is spot on. Textbook RSA is multiplicative so since $m_3=m_1 m_2,$ then $s_3=m_1^d m_2^d \pmod n=s_1 s_2 \pmod n.$ Magma tells me that $s_3$ should be 5483355855153602627619220309939701891434212768777923480007006960005208299649205 6581008264568421280116806103922182738655624242961539966642663712352455540402732 ...


2

Rather no. There is no standard construction going by the name Key Derivation Function aimed at generating public/private key pairs. Traditionally, especially for RSA, how to generate a key pair is left at the discretion of the implementation, rather than made per a specific deterministic process. The usual name is Key Generation. And it's usually stated as ...


2

The issue is, the message length is now longer than the modulus $p$ and $q$ That's not true. In the $p$ track, you are raising $M \bmod p$ to the power $d \bmod p-1$; we have $M \bmod p < p$; that is, the value we are exponentiating is less that $p$, as results by Montomery multiplication. In the same way, the $q$ track also satisfies the requirements ...


1

1. This is what you asked: How to declare such 2048 bit values in C. As i know that the data types like int , long ,long long int even are less than 64 bits. Please suggest. 2. You can use the The GNU MP Bignum Library. This is the manual. 3 This is how to declare such 2048 bit values in C using The GNU MP Bignum Library . // this is the big number p ...


1

what I am doing wrong? Accepting as fact a recipe with an equation, rather than deriving it. Illustration: « Then we obtain $m$ as ${c_1}^a + {c_2}^b \bmod n$ » is stated rather than derived. And wrong. As an aside the question reverses $a$ and $b$ (or is it $c_1$ and $c_2$, or $e_1$ and $e_2$): they are correct per the official solution which asks $a\,e_1 +...


1

Why is this a requirement? Well, if $r$ has (say) $p$ as a factor, then it makes the unblinding step rather difficult. The original $m$ has $N = pq$ possible, as does $m^d$; if $r$ is a multiple of $p$, then $mr^e$ has only $q$ possible values; if we pass it to the signer, it'll come back to us with a value $m'^d$ that also has only $q$ possible values. We ...


1

If you have $e$ ciphertexts for the same message, then the attack is the same, you just have to apply the CRT with $e$ values, then computing the $e$'th root of the resulting value might need some work. And this is assuming that all moduli are relatively prime of course. If that's not the case, there is $i,j$ and $gcd(N_i, N_j) \neq 1$. So you can factor ...


1

I assume this is homework (I have time imagining that this is a problem that you need to solve; if it is, turn "use real RSA padding"). Since this is assumed to be homework, I'll give you the initial steps, and let you do the rest of the work. First off, what you're asking is to find a value $m$ such that $(m^3 \bmod n) \bmod 2^{136 } = \text{"\x00"...


1

Besides the answer Dimitree gave to himself, I' like to add something even if I am not sure whether I understand the original problem he wanted to solve. You used the same message a and encrypted it with different values for e, but used the same modulus N. And you added the different exponents e. As far as I know, the homomorphic multiplicative feature of ...


1

The proposition following «show that» in the question's first paragraph requires $p\ne q$ to become true. Problems are that when $p=q$, the expression $\phi(n)=(p-1)(q-1)$ no longer holds, and even fixing it to $\phi(n)=(p-1)\,p$ does not make the proposition true for quite all $M$ and $e$, when $p\ne2$. For example the proposition fails for $p=q=M=3$, $n=9$,...


1

I am not too familiar with this paper, but there is (at least) the following reason. They define $\Delta = l!$, then require (right after equation 6) that $1 = \mathsf{gcd}(e', e) = \mathsf{gcd}(4\Delta^2, e) = \mathsf{gcd}(4(l!)^2, e)$. This is not possible if $e \leq l$ (as then the GCD is $e\neq 1$).


1

The correct form is: The integer $a \mod Z_n$ has multiplicative inverse iff $gcd(n,a)=1$ Here, you are working on exponents, so you must consider the modulo as $\phi(n)$ not $n$. Therefore, here you can find the inverse of $e$ iff $gcd(e, \phi(e))=1$. This guarantees that you be able to find the inverse of $e$ using extended Euclidean algorithm.


Only top voted, non community-wiki answers of a minimum length are eligible