Tag Info

New answers tagged

0

I have solved this problem. @fgrieu was right! Thanks for him and other! Calculating modular inverse if a < 0: _, eM1, __ = gmpy2.gcdext(eM1, N) elif b < 0: _, eM2, __ = gmpy2.gcdext(eM2, N) Calculating source message M M1 = pow(eM1, abs(a), N) #I just realized, that always i need to use modulus pow(a,b,n) M2 = pow(eM2, abs(b), N) #In ...


1

@CodesInChaos is right, here is an example of his method on your data : $40 = 2^3 5$ so I pick, say $e=3$, which is for sure coprime with $40$. Actually $e=3$ is a common value in some implementations of RSA (see @fgrieu giant response about that) By chance (or did you teacher foresaw it ?) Extended Euclidian Algo is pretty fast here : $40 = 13 \times 3 ...


1

1) Yes. This is the common modulus attack and has actually been answered many times on this forum. 2) Assuming $r$ is prime, yes. $\phi(n)$, (the totient of $n$) can be computed by subtracting 1 from each of $n$'s prime factors and multiplying them together.


9

The question asks how to systematically pick the public exponent $e$ in RSA. I'll stick to public modulus $N$ that is the product of exactly two distinct odd primes $p$ and $q$, but the choice of $e$ is not fundamentally different in multiprime RSA. What's an acceptable public exponent $e$? The public exponent in RSA should be an integer $e>1$ with ...


-1

Here is a blog post link: tominology For a sketch of proof using Fermat's little theorem and a simplified JavaScript implementation


1

It is extremely likely to be either RSA with PSS padding or RSA with PKCS#1 v1.5 padding, the latter being the most likely. If you sign two times and the output is twice the same then it is not PSS and PKCS#1 v1.5 would be the prime suspect (that was my brain making fun of me, pun not intended). RSASSA-PSS is different from other RSA-based signature ...


1

The "normal", unmodified RSA (called textbook RSA) is susceptible to some attacks. We need to change it slightly to avoid this problems. The question Definition of Textbook RSA and the Wikipedia lists some possible attacks. In practice a special padding algorithm is used, like the Optimal asymmetric encryption padding (OAEP). The documentation of the ...


0

This is done by the server recording all public keys of all clients and presenting them (usually on demand per client). This allows a client to generate an AES key (or replay it) as a secret message to any other client without the server knowing what it is. An extra protocol layer is required where the server's exchange with the client is somehow signed (or ...


3

The only way you could do this if if you could affect the padding schemes appropriately. Mathematically, textbook RSA encryption with the private key is the same as textbook RSA signature generation. Nobody should use textbook RSA, however. In practice, padding schemes are used and they differ between the two operations. So unless you can turn off padding ...


4

Yes, you can, but you would need access to raw or textbook RSA encryption and you would have to implement the PKCS#1 v1.5 or PSS padding primitives yourself. Beware that PKCS#1 v1.5 compatible padding is different for encryption signature generation. If you only have PKCS#1 v1.5 encryption or OAEP encryption available then the encryption routine will ...


0

Given that you used a strong password to derive the AES encryption key: Yes you could securely store your RSA private key in encrypted form on a server. BUT, since there is no technical need to have your private key on the server, why would you risk it? Look at it that way: Suppose you have very sensible data (like private photos or so). Now you could ...


2

This is called the common modulus attack. Bezout's Identity says that there exists $x$ and $y$ such that $ax + by = gcd(a, b)$. In our case we have $gcd(e_a,e_b) = 1$, so we can find $x$ and $y$ such that $e_{a}x + e_{b}y = 1$ (you can use the extended euclidean algorithm for this). After solving for $x$ and $y$, you compute: $C^xC^y\mod N$ to get $M$. ...


2

It's a consequence of the Chinese Remainder Theorem (look it up, if you don't know it) if you want to be more precise and understand it algebraically. If $n=pq$ and $de \equiv 1\;(\textrm{mod }\phi(n))$, then we also have that $$de \equiv 1\;(\textrm{mod }p-1),\;\;de \equiv 1\;(\textrm{mod }q-1),$$ since $\phi(n)=(p-1)(q-1)$. It follows that for any ...


2

Textbook RSA encryption scheme is not IND-CPA secure as it is a deterministic scheme. Textbook RSA signature scheme is not secure considering Existential Unforgability under Chosen Message Attack. e.g. if attacker $\mathcal{A}$ chooses random x $\in$ {1,2,...,n-1} and computes y = x$^{e}$ mod n, then sets m = y, $\sigma_{m}$ = x then $\sigma_{m}$ is a valid ...


4

This describes some attacks against textbook RSA (also known as raw RSA), where the public or private functions $x\to y=x^e\bmod N$ or $y\to x=y^d\bmod N$ are applied directly to the message. Encryption / Decryption Determinism in textbook RSA allows an attacker - given a ciphertext - to search for the corresponding plaintext. Determinism also leads to ...


2

In RSA, the modulus is computed as $n=pq$ where $p$ and $q$ are prime. Given two moduli, if they have no primes in common, then the GCD is $1$ and they are relatively prime. If they share a prime factor, then the GCD will reveal that prime factor. Therefore, anyone who knows the two public keys can factorize the moduli and break security.


0

Why can't you use RSA? Look at their description of a function on pp. 41-42, and you'll see that it is a perfectly valid choice. So you have two users, $A$ and $B$, who want to play. One user, say $A$, selects $p \cdot q = n$, as per $RSA$, and sends that information to $B$. Both $A$ and $B$ independently choose large primes (or large numbers they confirm ...


4

You've mostly pieced it out. This is a DER encoding the the public key, and consists of a sequence of two integers (the first being the modulus, and the second being the exponent). Here is the breakdown of the encoding: 30 The value 30 is used to signify 'sequence'; this is a container that carries a list of DER-encoded objects. 82 01 0a Whenever we ...


0

Are there fallacies in above argumentation and is it a reasonable scheme? It's not unheard of to encrypt secrets for them to be decrypted by a HSM or smart card. Usually though the smart card or HSM itself is used to encrypt/decrypt stored secret values. I know that at least one HSM does this, and all TPM's out there. If you are accepting an unlimited ...


3

Okay, I came up with this, it's not a complete answer and the attack presented is pretty weak without a follow-up algorithm for breaking a somewhat unbalanced modulus but let me know if you spot any flaws or have any ideas to improve it... If $n = pq$ with $p, q$ prime and $\gcd(pq, (p - 1)(q - 1)) = r > 1$ then clearly $r = p$ or $r = q$. Now ...


0

I'm sorry @J0ker, I found new answer (maybe there are errors value in my first answer). My new answer $m =$ 49314552466695255586203088029816774295110376055124609941914798033775741215800363731230533018093001338140450279336308798327354131807371119497156895131357788895448541113895626439002123851 I try to convert $m$ to base 256 [75, 110, 111, 119, 108, ...


4

Yes; as long as the product of the two plaintexts $p_1 \cdot p_2 < N$, you'll get their product; it doesn't matter what the ciphertext values actually are. The relevant question is: what happens if the plaintexts overflow; that is, what if $p_1 \cdot p_2 \ge N$? In that case, when you decrypt, you'll get the result $p_1 \cdot p_2 \bmod N$


0

We have $d = e^{-1} \pmod{ \phi(N) }$, this implies that $m = c ^ d \pmod{N}$


1

The main problem here is that signature is malleable. Given signatures on $m_1$ and $m_2$ allows you to construct a valid signature on $m_1m_2$ by multiplying the signatures. Therefore, the answer is no. When you hash you don't have $H(m_1m_2)=H(m_1)H(m_2)$, so hashing destroys this algebraic structure that connects messages and signatures. EDIT: I'm ...


2

RSA CRT (with $N$ the product of two distinct primes $p$ and $q$) implements the $x\to y=x^d\bmod N$ private-key function by computing $y_p=x^d\bmod p$ and $y_q=x^d\bmod q$; then combining $y_p$ and $y_q$ into the desired $y$ by constructing the solution to the equations $y\equiv y_p\pmod p$, $y\equiv y_q\pmod q$, $0\le y<N$, with that last step requiring ...


2

Using randomization on the RSA key before encryption doesn't work as easy as a simple XOR: the key (or actually, key pair) has some complicated mathematical structure, and the public part of it (the modulus and the public exponent) need to be known by the encrypting party. What might be possible would be to randomly chose the encryption exponent, and ...


0

The key you wrote down contains a mixed alphabetic and digit symbols because it is written in its hexadecimal representation: i.e. using symbols from 0 to 9 and from A to F. More on this topic on Wikipedia page. You can easily convert hexadecimal to decimal using software as python, sage, Pari/GP and many others. An online converter could be found here: ...


1

I might be giving out too much information here (so don't read unless you want spoilers). Anyway, as rings the Chinese Remainder Theorem gives $$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z}\times \mathbb{Z}/q\mathbb{Z}$$ The isomorphism takes $(\mathbb{Z}/n\mathbb{Z})^\times$ to $(\mathbb{Z}/p\mathbb{Z})^\times \times ...


1

Hint: try to prove that $a^{phi(n)/g} \equiv 1 \pmod p$ for all $a$ satisfying $gcd(a, n) = 1$. Metahint: $phi(n)/g = (p-1) \times (q-1)/g$; is $(q-1)/g$ an integer?


4

$q$ does not divide $s^e-h(m)$, but $p$ does, so since the gcd must divide both $s^e-h(m)$ and $n$ it's $p$. To be even more explicit, we know that $p$ divides both $s^e-h(m)$ and $n$. The only larger divisor of $n$ that is also divisible by $p$ is $n$ itself, but if $n$ would divide $s^e-h(m)$, then $q$ would also divide $s^e-h(m)$, which we already assumed ...


2

The following potential reasons occur to me why someone might not choose to use the CRT optimization: The implementor worries about induced faults (but not quite enough to implement the obvious protection against it). That is, with the CRT optimization, we process the RSA block both mod p and mod q separately, and then combine them. That means that if ...


1

It is generally applied as far as I know. One thing that makes it tricky to implement in some situations is that it may be more vulnerable to certain side channel and fault injection attacks than "straight" RSA. Those attacks may expose the prime factors and thus the private key. I cannot see other reasons why it wouldn't be implementable on some platforms, ...



Top 50 recent answers are included