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

0
votes
1answer
64 views

Questions about length key of RSA 2048 bit

I use putty gen to generate RSA key, I choose length of key is 2048 bit, it generate public key: ...
0
votes
0answers
24 views

Diffie-Hellman combined with DSA/RSA

we have learned Diffie-Hellman, RSA and DSA (Digital Signature Algorithm) in university. Because DH is vulnerable of Man-in-the-Middle we had the task to program the DH combined with RSA to protect ...
0
votes
1answer
33 views

factorization of an integer $N$ that is in special format

Suppose $p_0$ and $q_0$ are known prime numbers and define $p_i$ and $q_i$ as follows: $$p_{i+1} = next\_prime(p_i^2 + q_i^2), \qquad i \ge 0$$ and $$q_{i+1} = next\_prime(2p_iq_i), \qquad i \ge 0$$ ...
1
vote
0answers
33 views

Are public key and private key exchangeable? [duplicate]

If I get a key pair from RSA algorithm, can I make Private-Key public, and keep Public-Key secret without breaking the security of encryption and signature?
48
votes
6answers
36k views

How can I generate large prime numbers for RSA?

What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption? I'm aware that I can find any number of articles on the Internet that explain how ...
5
votes
1answer
276 views

How long does it take to decrypt an RSA/ECB encrypted message?

I am working on assignment where I have specific scenarios and I am little bit struggling with this one. Alice sends and email to Bob.For this e-mail, she uses the following method of encryption: ...
7
votes
2answers
385 views

Can Shor's algorithm compromise RSA when both the public and private key are secret?

If RSA is to create a public private key pair and encryption is performed on plain test P to create cipher text C, given P and C could Shor's algorithm be used to find either of the public and private ...
3
votes
2answers
3k views

How to calculate the maximum output size for data encrypted with a RSA Private Key?

I have an an encryption algorithm I am working with that looks like this: prv_key_enc(sha1_hash(data)) Where, the RSA parameters are: RSA/ECB/PKCS1Padding 1024 ...
6
votes
0answers
58 views

Name of an archaic type of RSA padding (0BBBBBBB…)

In some legacy code, I encountered RSA signature padding in the following format (hexadecimal): 0B BB BB BB BB BB BB ... BB BB <hash> Is there a name for ...
1
vote
0answers
50 views

How can I obtain the raw decimal value of an RSA key's modulus?

So maybe I'm thinking about this too hard, or maybe I'm missing a piece of information. We'll use Google for this example. Say I wanted to obtain the modulus of Google's current public key. Well I ...
2
votes
1answer
62 views

How to prove a lemma that is based on phi-hiding assumption?

Assume that the $\phi$-hiding assumption is true, i.e. that for a composite number $m$, a PPT adversary A cannot distinguish between a prime $p_0$ that divides $\phi(m)$ and another prime $p_1$ that ...
3
votes
1answer
89 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?
0
votes
0answers
46 views

How to encrypt huge data using RSA? [duplicate]

Is there any way to encrypt the huge amount of data using RSA? I was supposed it is possible but when I read some articles what I saw is that, this is bad practice or they say can only encrypt bit ...
3
votes
1answer
38 views

Is there a way to turn a PGP key into its semi-prime counterpart?

From my understanding of PGP keys they use the RSA algorithms to encrypt/decrypt messages. So, I know that the RSA algorithms use a semi-prime number to encrypt/decrypt messages. So, what I was ...
0
votes
0answers
74 views

RSA PlainText without Knowing Private Key

I couldn't solve this problem for three days... In RSA, [n = 13, 19] [e = 3] c1 = m^3 = 83 mod 247 [e=5] c2 = m^5 = 97 mod 247 then, use ...
3
votes
1answer
79 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 ...
35
votes
11answers
8k views

Now that quantum computers have been out for a while, has RSA been cracked?

D-wave systems has released a commercially viable quantum computer. This means in theory, that all asymmetric encryption algorithms — such as RSA — are now useless due to the speed at which quantum ...
0
votes
2answers
74 views

Factoring an RSA modulus given high bits of a factor

I have {e,N,C} and part of p; can I get q from this example : ...
4
votes
1answer
128 views

Why does choosing the first coprime e greater than half of φ(n) result in the same d (private exponent)

While reading on RSA's algorithm, I attempted a simplified implementation and noticed the following: When choosing the public exponent $e$, if the value chosen is the first coprime after $φ(n)/2$ ...
20
votes
4answers
7k views

Security strength of RSA in relation with the modulus size

NIST SP 800-57 §5.6.1 p.62–64 specifies a correspondence between RSA modulus size $n$ and expected security strength $s$ in bits: ...
0
votes
1answer
56 views

How to use the hardcoded server's public key to register a client application?

I'm designing the security for a smartphone app that can be used to make car reservations. Clients have to register them with their driver's licence through the application and can then book a car. ...
3
votes
1answer
36 views

How does this solution guarantee authentication of B and privacy?

The exercise is: What could be changed on the second message " Kya(Kxb(Ra,Ks)) " to guarantee B's authenthicity and also privacy? My teacher's solution was "add a destination" , so it would be ...
3
votes
1answer
54 views

Need help understanding this exercise's solution

We were given this exercise, which asks us to identify the types of keys used on this diagram: The solution was Kxa -> A's private key Kya -> A's public key KxB -> B's private key My question ...
1
vote
1answer
64 views

Factorization of RSA modulus using a qubic residue

Suppose that someone uses RSA with $n = pq$, exponent $3$, also $3$ divides $\varphi(n) = (p-1)(q-1)$ and $2$ different roots $y$ and $z$ of the equation: $$x \equiv c \ (mod \ n)$$ are known (for ...
3
votes
2answers
83 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)=...
0
votes
1answer
19 views

Digital signature with collision

Let's assume a digital signature scheme such that there's a probability of 0.2 for two random messages to have the same signature. How can I exploit this sheme? I'm having difficulties in finding an ...
0
votes
1answer
25 views

X509 Cert exploit CA check

Assumptions Let's theoretically assume that a browser skips the check that a certificate it receives belongs to the stated CA (that's an exercise). How could I exploit this in order to impersonate ...
0
votes
1answer
55 views

Why is it better to have the private key as the multiplicative inverse mod phi(n) in RSA?

I'm studying the RSA algorithm and the theory says to select $d$ to be the multiplicative inverse of. $$ e \mod \phi(n) $$ If we take this approach I know that it is important that $e$ and $\phi(...
1
vote
0answers
39 views

Issue Factorization Quadratic Sieve

Good evening, I'm about to write my own quadratic sieve implementation in C using GMP library for large numbers. I'm facing an issue while attempting to do the last factorization step for the number: ...
0
votes
3answers
116 views

Can $d$ and $e$ be the same number in RSA?

I'm reading about RSA and I have doubts: 1) To choose $e$, this value have to be between $1$ and $\phi=(p-1)(q-1)$, with $\gcd(\phi, e) = 1$, right? 2) In my example, $p = 139$ and $q = 491$. So $n =...
12
votes
4answers
1k views

Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC)?

Related to "Is it possible to derive the encryption method from encrypted text?". Given ciphertexts generated by any of the major asymmetric ciphers (RSA, ElGamal, ECC, etc..) can these ciphertexts ...
1
vote
2answers
75 views

Why is padding the plaintext with a random string before encryption worse than OAEP / PKCS#7?

I'm reading about OAEP / PKCS padding used for PGP to turn deterministic algorithms like RSA from deterministic encryption to probabilistic encryption (randomness in the resulting output). That way ...
4
votes
1answer
433 views

How to sign a large file for random-access reading?

I need to write an "Authoring" application which produces large files. These files must be signed so that the "Consuming" application knows that it was authored with a matching key. The consuming ...
16
votes
9answers
5k views

RSA with small exponents?

Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse ...
19
votes
4answers
4k views

Why does RSA need p and q to be prime numbers?

This is a clarifying thread after finding: What makes RSA secure by using prime numbers?. Despite the fact that this question was answered already, I am still struggling to really grasp the ...
3
votes
0answers
103 views

How to generate an RSASSA-PSS signature with MGF1-SHA256?

As part of rooting a device, I need to generate a 256-byte RSASSA-PSS signature using SHA256 as the hash and MGF1-SHA256 as the mask function, for an update file I created. I can choose any 32-byte ...
3
votes
3answers
117 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 ...
4
votes
2answers
707 views

Calculate the RSA private exponent from the CRT parameters

I am trying to make the RSA structure of Openssl manually, knowing the public key ($n$, $e$) and the CRT parameters $p$, $q$, $d_P$, $d_Q$, and $u = q^{-1} \mod p$. That is, I want to get the $d$ ...
4
votes
2answers
125 views

RSA 3072 is 65,536 more difficult to factor than 2048?

If RSA 3072 is equal to 128 bit symmetric and 2048 is equal to 112 bit symmetric then 128-112= 16 and 2^16= 65,536. In that case wouldn't this make 3072 more future proof against quantum computers or ...
9
votes
2answers
11k views

What makes RSA secure by using prime numbers?

I am just learning about the RSA algorithm. Looking at the first two steps: Choose two distinct prime numbers $p$ and $q$. Compute $n = pq$. I have some probably stupid questions: Why do $p$ ...
4
votes
1answer
139 views

What is the major difference between FIPS 186-2 and FIPS 186-4?

Can anyone please tell me the major difference between FIPS 186-2 and FIPS 186-4? I know with FIPS 140-2 they want the DSS standard to be FIPS 186-4, but what difference does it make?
0
votes
1answer
91 views

New Improved Probabilistic version of RSA

On the 2nd page of "New probabilistic public-key encryption based on the RSA cryptosystem" by Roman'kov (PDF), at last it says Alice can find "f" of order "l" with least probability of (1-1/l). I ...
1
vote
1answer
31 views

How to add passphrase to an RSA key?

If I want to protect a private RSA key, do I just XOR the password into the key, or do I do something else? Is it secure? Edit: I got a good answer from a comment - Hash the password/passphrase with ...
3
votes
1answer
188 views

What is the probability of attacking SHA1 used in RSA signature with small exponent?

There is RSA signature check which has following properties: RSA modulus N which is 2048-bit RSA public exponent equal 41 (0x29) Genuine Signature uses EMSA-PKCS1-v1_5 padding of SHA1 hash, however ...
21
votes
2answers
2k views

Why is PuTTYgen-created RSA public exponent(e) not in {3,17,65537}?

As far as I know, RSA public exponent(e) should be one of {3,17,65537}. However, I found PuTTYgen-created RSA public exponent(e) is 0x25(37) by default,as follows, (PuTTYgen version: 0.66) I am ...
0
votes
1answer
46 views

How do you work out the private key in a RSA cryptosystem knowing a certain public key?

The public key: n = 85 and e = 19 I know that n is the product of two prime numbers, now is it right of me to figure them out by process of elimination which I got p or q equals 17 and 5. Or is ...
2
votes
1answer
99 views

RSA Encryption problem for Discrete Math

I am doing practice problems for my upcoming final exam, and am having trouble with this RSA encryption problem. If any one could check to see if i did these correctly, it would be greatly appreciated....
2
votes
1answer
60 views

How can I show RSA OAEP IND-CPA secure

How can I show, that RSA with OAEP is IND-CPA secure by using G,H one way function?
5
votes
2answers
178 views

Should RSA primes p and q differ in length by “a few digits”?

When generating RSA keys in the original RSA paper it is stated: to gain additional protection against sophisticated factoring algorithms, p and q should differ in length by a few digits Why is ...
1
vote
0answers
53 views

Encrypting/Decrypting using RSA and AES; standards?

I'm looking for a standard way of encrypting and signing a message using RSA and AES. I understand that in pseudo code the actions taking place are like this: Alice's actions for sending a secret, ...