an asymmetric (e.g. public-key) cryptosystem, based on modular exponentiation with big exponents and modulus. RSA can be used both for signature and encryption.

learn more… | top users | synonyms

3
votes
2answers
598 views

RSA performance

I was wondering what is the performance bottleneck in RSA algorithm? Is it the size of message, calculating the modular inverse, exponentiation? Say I have a fixed value of n to encrypt and decrypt ...
3
votes
4answers
3k views

Why is RSA encryption significantly faster than decryption?

I am designing an implementation of RSA . I recorded computation times in Java by using System.currentTimeMillis(). It returned an encryption time of 0.05 ms and ...
3
votes
3answers
233 views

Can the encryption exponent e be greater than ϕ(N)?

So I was just wondering in RSA, can the encryption exponent e be greater than ϕ(N)?? For an examples sake, lets just say N = 707, so p = 101 & q = 7. So, we have ϕ(707) = 600. Can I have e = 707?...
3
votes
2answers
308 views

RSA: Recover e given factorization of N and plaintext/ciphertext pair

Is there a way to recover the public exponent e (assume in this case it is in fact not public) used in an encryption if I know the following: Factorization of <...
3
votes
2answers
413 views

Avoiding overflow when encrypting with RSA

When encrypting with RSA one calculates $ m^e \pmod n $ by doing the following: m^e % n Where $m$ is what we encrypt. Often $e$ is a very big number to make it ...
3
votes
1answer
792 views

What's the main difference between Pohlig-Hellman and RSA?

Both Pohlig-Hellman and RSA perform encryption and decryption by exponentiation modulo some integer ($p$ prime for PH, $n$ composite for RSA). They both use a key $e$ as the exponent to encrypt a ...
3
votes
1answer
1k views

Is RSA of a random nonce with no padding safe?

Consider the following protocol: Bob has a private RSA key $B_{priv}$, and Alice knows the public key $B_{pub}$. Alice wants to send confidential messages to Bob (no integrity intended). To send a ...
3
votes
2answers
279 views

Isn't the deterministic property of (EC)DSA a security problem?

From what I read in Wikipedia's article "Elliptic Curve DSA ~ Security", the "deterministic" generation of $k$ can help prevent certain type of attacks (such as the one happened to Sony). However, ...
3
votes
1answer
743 views

Textbook-RSA meet-in-the-middle attack against other RSA based schemes?

A “meet-in-the-middle” (not “man-in-the-middle”!) attack on textbook-RSA was presented to me. The only requirements for it was that the attacker gets the output of RSA and the public key, and that the ...
3
votes
4answers
934 views

RSA by hand - did I do something wrong? (c = m on encryption)

to understand RSA better I am doing a little calculation by hand, this is what I got: Choosing: $p = 3$ $q = 5$ $n = 15$ $\phi(pq) = 2 \cdot 4 = 8$ $e > \phi(n) => e = 13$ $e \cdot d = 1 \...
3
votes
2answers
1k views

Difficulty of breaking RSA for a given key size

Is it true that breaking a 1024-bit RSA key is as difficult as breaking a 128 bit symmetric key (e.g. AES)? I know that breaking a RSA key is equivalent to factoring the modulus $N$. To factor it, you ...
3
votes
2answers
253 views

Finding Private key in RSA with public key, cipher text and plain text

Is there a known 'non-brute force' method of determining a private key in an RSA system when all other parameters are know? I found the values of a ciphertext ($C$), its corresponding plaintext ($P$) ...
3
votes
1answer
129 views

How do I attack an RSA setup where e is even?

As a challenge, we were shown an RSA setup where we have a big $n$ (617 decimal digits), $e=4$, and asked to recover three messages. (However, the messages are padded to the same length as the key ...
3
votes
2answers
247 views

Perfect Forward Secrecy in TLS

I read that TLS does PFS using Diffie Hellman. However, DH can be used even without certificates - so how is DHE-RSA better than plain DHE? Is DHE a insecure algorithm, that DHE-RSA is needed?
3
votes
2answers
2k views

What does an RSA signature look like?

I am using OpenSSL libs to generate signatures. Internally, I learn that a signature is a hash of the message with some padding added to it. I am trying to understand the structure of a signature. If ...
3
votes
2answers
1k views

Openssl & RSA : how many public exponents are possible?

I would like to know if it is possible to set the public exponent we want with "OpenSSL RSA" or if it is really limited to 2 possible exponents: 3 65537 If yes, why ?
3
votes
2answers
927 views

If we can find prime numbers larger than 17 milion digits, why can't we find all 1024bit primes? [duplicate]

"Largest Known Prime Number Discovered; Has 17,425,170 Digits" http://www.sciencedaily.com/releases/2013/02/130213225424.htm If we can find prime numbers larger than 17 milion digits, why can't we ...
3
votes
3answers
1k views

If RSA is limited to 117-200 bytes or so, is that a very limited use case?

Am I missing something, or is RSA very very limiting when it comes to ecrypting data when it comes to the actual message size? I have read that you can only encrypt a message of around 117 to 200 ...
3
votes
1answer
1k views

Why do we need in RSA the modulus to be product of 2 primes?

I think I roughly understand how the RSA alorithm is working. However, I don't understand why we need the $N$, which we use as a modulus, to be $pq$ for some large primes $p, q$. I vaguely know it ...
3
votes
2answers
1k views

How to decrypt this RSA-like cipher

Suppose we have a RSA-type Modulus $n = pq$ with $p,q$ prime. We also pick a random public exponent $e$ with $\gcd(e,\varphi(n)) = 1$ and compute the private exponent $d$ with $de \equiv 1 \pmod{\...
3
votes
2answers
609 views

How does the cyclic attack on RSA work?

I am trying to get the idea of cyclic attacks againts assymetric RSA encryption. Taken from Handbook of applied cryptography . Let $k$ be a positive integer such that $$c^{(e^{k})} = c\mod n \tag{1}....
3
votes
2answers
154 views

Why do we need Euler's totient function $\varphi(N)$ in RSA?

After we calculated $N = p * q$, we calculate $\varphi(N)$ and use it later to determine $e$ (PR) and $d$ (PU). But why? For decryption and encryption we only use $N$ and don't need $\varphi(N)$. So ...
3
votes
2answers
241 views

Why are recomended RSA key lengths so high? [duplicate]

I was checking for authoritative sources to back up my recommendation of a minimum RSA key length of 1024 and was shocked to find that NIST 800-56Br1 and FIPS 186-4 both recommend at least 2048 bits ...
3
votes
1answer
170 views

RSA private key finding method

Bob uses RSA with $p=83$ and $q=103$. His public key is $e=445$. Alice claims that she can calculate Bob's private key without using the definition $d=e^{−1}\bmod φ(n)$? But how?
3
votes
1answer
169 views

Checking the integrity of RSA public key

Let's say I need to verify a digital signature and the public key is stored in untrusted storage which I need to fetch before I verify the digital signature. However, I can store the cryptographic ...
3
votes
1answer
133 views

Relationship between exponent and modulus in RSA (as RSA properties as listed in X.509)

In one of my assignments, I had the following question (Please read on. Not a homework assignment :) ): X.509 (1998 version) lists properties that RSA keys must satisfy to be secure. One such ...
3
votes
1answer
90 views

For which RSA moduli, precisely, is $e=d$ for all $e$?

This question shows that there are at least two valid RSA moduli $n$, namely $35$ and $91$, such that for any $e$ coprime to $\lambda(n)$, $$e^2\equiv1\mod\lambda(n)\text.$$ Reading the linked ...
3
votes
2answers
1k views

Chosen plaintext attack on textbook RSA decryption

Let $(n,d)$ be an RSA private key and $(n,e)$ the corresponding public key. Generate a secret random $r$ from $(\mathbb{Z}/n\mathbb{Z})^*$ Compute $C’ = C (r^e) \bmod n$ Submit $C’$ as a chosen ...
3
votes
2answers
4k views

At what stage is DHE and RSA used during the SSL/TLS handshake?

At what stage of the SSL/TLS handshake is the DHE and RSA used and what is the purpose of using a pre-master secret when you could just use RSA to exchange the symmetric key (i.e. AES) for further ...
3
votes
1answer
348 views

RSA Key generation Public exponent too big

I'm currently writing a paper about RSA (a self-chosen subject). I'm writing about the key-generation in RSA, and I have problem finding the public exponent e. I have chosen p = 61 and q = 53. Then ...
3
votes
1answer
84 views

RSA Digital Signature vs Elgamal Digital Signature

What are the advantages of RSA signatures against ElGamal signatures? Is there a situation in which it would be better e.g. to use RSA signatures?
3
votes
1answer
76 views

Highest prime factor that is Safe for a particular scheme

My question is how many bits of prime number is secure so that it cannot be factored from very large number? Until today how large prime factor is found in large number? Quantum computing find ...
3
votes
2answers
70 views

Chosen-Message-Attack RSA-Signature

I know that because of the multplicative property of RSA $s =(s_1s_2) \bmod n = (m_1m_2)^d \bmod n$ If Oscar wants to sign now an own message $m$ he chooses another message $m_1$ with $\gcd(m_1,n)=...
3
votes
3answers
109 views

Can an adversary distinguish a private key from a pseudo-random string of the same length?

Apologies if this is a dumb question but allow me to describe the dilemma I have: Suppose that I am protecting a private key on a device using a password & PBKDF2. The obvious attack would be an ...
3
votes
2answers
71 views

RSA: select $e$ given $n$ and $\varphi(n)$

I have a question for a course I am doing. In an RSA question, it asks "Is it possible to select $e$ in such a way that it coincides with the corresponding private key $d$? If it is possible, provide ...
3
votes
1answer
55 views

Selective and existential unforgability of signature schemes

I understand that one can define EUF-CMA of a signature scheme is terms of a game where the adversary is allowed to query signatures on messages of his choosing, and at the end of the game he must ...
3
votes
1answer
110 views

Should I be concerned about padding oracle attacks if the lifespan of my key is ~1 minute?

I'm using 4096-bit RSA to encrypt a 256-bit AES key generated client-side. The RSA ciphertext is then sent to the server, and the server decrypts the RSA ciphertext to acquire the AES key. ...
3
votes
1answer
75 views

RSA: Range of public modulus

I know the public modulus is the product of two primes. For key with length L, the public modulus N should be such ...
3
votes
1answer
140 views

RSA with $\lambda(n)$ or $\varphi(n)$

The PKCS #1 v2.0 specifications suggest using $\lambda(n) = \mathrm{lcm}(p-1,q-1)$. What is the benefit of choosing $\lambda(n)$ over $\varphi(n) = (p-1)(q-1)$ in RSA key generation?
3
votes
2answers
209 views

Attacking unuauthenticated RSA

In symmetric cryptography, a scheme is not considered secure if the data transmitted is only encrypted. The adversary will be able to modify messages to generate encrypted messages of his choice ...
3
votes
1answer
1k views

Montgomery Ladder vs Double-and-Add

I would like to know what (if any) are the advantages of using Montgomery Power ladder over the Double-and-Add-Always algorithm. I think that firstly, Monty would be slightly faster than DoubleAndAdd. ...
3
votes
2answers
389 views

Is it possible that two distinct RSA moduli share both of their prime factors?

I am using an algorithm (can be found here1) that can compute efficiently the GCD of multiple RSA keys. It intended for RSA keys that were generated with low entropy and may have one of their primes ...
3
votes
2answers
960 views

risk of attacker decrypting RSA ciphertext without public or private key

As I describe in my previous question I am trying to decide if it's worth it for me to use the Offline Private Key Protocol in creating some long term private archives, instead of just going with a ...
3
votes
1answer
700 views

Cracking an RSA with no padding and very small e

I have a project wherein I have to crack a given cipher text encrypted using RSA and have been given N and e. Can someone suggest an RSA attack using a very small exponent e(here e=3) and no padding?
3
votes
1answer
430 views

Is it possible to determine the group order by knowing the “public” and “private” key exponents in an RSA group?

I have an RSA group with modulus $n = p \cdot q$, two safe primes $p=2p'+1$ and $q=2q'+1$ and the "public" and "private" key exponents $d$ and $e$. $\phi(n) = 4p'q'$ is the order of the RSA group. If ...
3
votes
1answer
552 views

Why is RSA usually limited to messages up to 1 block

I'm wondering why RSA encryption usually is only used for messages that fit into one block. For larger messages hybrid encryption in combination with symmetric ciphers like AES seem to be the solution ...
3
votes
1answer
294 views

RSA Without Padding?

I've been looking at the weakness with plain/textbook RSA, where the same message is encrypted and sent to multiple destinations. In this case, it is possible to recover the message. Given that an ...
3
votes
1answer
2k views

“Signing” with public key

For this question, the following caveats and assumptions hold: There exists a 2048-bit RSA key pair used exclusively for signing/verification The private key is kept completely private There exists ...
3
votes
2answers
585 views

Is it possible to figure out the public key from encrypted text?

Suppose Alice sends messages to Bob by encrypting the messages with Bob's public key. Eve knows that the data is encrypted using RSA, but does not know the public key. Can Eve figure out the public ...
3
votes
1answer
5k views

RSA cracking: The same message is sent to two different people problem

Suppose we have two people: Smith and Jones. Smith public key is e=9, n=179 and Jones public key is e=13, n=179. Bob sends to ...