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

1
vote
1answer
27 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
59 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 ...
2
votes
1answer
117 views

RSA: special parameters construction

I have to show that the following construction of $q$ allows to factorize $N$ : $p \in \mathbb{P}$, the set of primes $q \gets p \cdot \left((p - 1)^{-1} \bmod e\right) \bmod e$ $k=1$ while $q \not ...
0
votes
1answer
17 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
23 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
54 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 ...
33
votes
5answers
6k views

In RSA, how does the CPU deal with this huge modulus (8192 bits)?

Whilst I understand how the RSA algorithm works, I don't understand how the CPU operates when it needs to use the mod function with a huge number $n$, for example. ...
1
vote
0answers
36 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
106 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 ...
0
votes
1answer
43 views

What is proper size of window Using RSA Window method?

I want to Use Window method for RSA modular Exponentiation. because of SCA. But I don`t know what is proper window size.
1
vote
2answers
45 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
427 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 ...
18
votes
4answers
3k 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
60 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 ...
-2
votes
0answers
24 views

How to know the size of an encrypted key that is encrypted using public key

I encrypted a key with a size of 32 bytes. I encrypted it using a public key. How will I know how big is the encrypted key(ciph)? My code: ...
3
votes
3answers
94 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
642 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
99 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 ...
8
votes
3answers
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
71 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?
2
votes
1answer
233 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: ...
0
votes
1answer
88 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
26 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
151 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 ...
-1
votes
1answer
43 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
92 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 ...
0
votes
1answer
58 views

How to decrypt an RSA ciphertext given an oracle providing the lower 8 bits of decryptions?

I have access to an oracle that can encrypt and partially decrypt a number with RSA-1024 algorithm. For encryption: \begin{equation} C = M^e\bmod n \end{equation} But for decryption, result will ...
2
votes
1answer
57 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
152 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
46 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, ...
3
votes
2answers
70 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 ...
6
votes
1answer
168 views

How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer?

So in the news this week, IBM have created a universal quantum computer with 5 fully functional qubits. Logic and Moore's law dictates they will be able to scale this up to a lot more qubits within a ...
-4
votes
1answer
61 views

How to find $e$ when $p,q,d$ are given?

I have solved till here ..... $$n=p*q$$ $$n=5*11$$ $$\varphi(n)=(p-1)*(q-1)=4*10=40$$ Now, how to find $e$, when $d$ is given as $27$ and message for encryption is $\text{abcdefghij}$. We have to take ...
-2
votes
1answer
84 views

Decrypting an RSA message given $a^2 \equiv 1 \pmod n$

I need help with a practice problem for an upcoming test. I've learned the answer to the problem is "well done", but don't know how to get there. Any help is greatly appreciated. Suppose that the ...
6
votes
3answers
11k views

The modulus of RSA public key

I am studying the RSA cryptosystem. The public key consists of $(n, e)$, the modulus (product of two large primes), and the encryption exponent. I want to separate the modulus $n$ and exponent $e$. A ...
9
votes
1answer
251 views

Algorithm for Boneh and Durfee attack on RSA

I am trying to understand various attacks on RSA and I believe that they only way to fully understand the algorithm is to implement it. I am trying to implement the code in this paper (pdf) (Private ...
0
votes
2answers
131 views

Where is the mistake in my RSA by-hand calculation?

Like several previous askers, I seem to have made a mistake in my RSA calculation, but despite going back over it three times, I cannot spot it. I picked 1000003 and 6000011 as my primes, ...
0
votes
2answers
127 views

How does SSL work on the browser

I recently bought an SSL certificate from a website and was able to make it work on my Apache server. As far as I know, it uses asymmetric keys and the private key is stored on the server while the ...
0
votes
0answers
16 views

Securely register a client in server using AES an RSA

I've designed the following protocol to send the client's public key to the server. Initially, the client knows server's public key, but the server does not know the client's public key. client ...
0
votes
1answer
30 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. ...
1
vote
0answers
54 views

Is it possible to enumerate the possible RSA keys? [duplicate]

As far as I understand ECDSA keys are smaller than RSA because all of the value of the ECDSA (up to a high number) are valid private keys. Is there any method of compressing RSA keys, based on some ...
7
votes
1answer
330 views

Blinding twice in RSA

I understand that if you have a message $m$, you can blind it by selecting a random $r$ and then multiplying $r^e\times m \pmod{n}$ Someone else then signs it with $d$, raising to the power of $d$: ...
1
vote
1answer
42 views

Can I get successful signature verification with just altering message and signature?

Assuming I can modify a message and also modify the verification signature, and I also have the public-key but not the private-key. Can I create a message that can be verified with a signature that I ...
2
votes
1answer
245 views

RSA signatures without padding

Suppose I have a message $M$ for which I generate an RSA-2048 digital signature as follows: $H = H(M)$, $H(M)$ being the SHA-256 of the message $M$ $S = H^d \bmod N$ Assume $N = pq$ is properly ...
6
votes
2answers
5k views

Why can’t DSA be used for encryption?

This question at StackOverflow mentions that DSA cannot be used for encrypt. But Both RSA and DSA can be used to generate public and private keys, right? (Or am I wrong?). Then why can't I use the ...
0
votes
0answers
17 views

Is AES-256 bit encryption secure against this kind of attack? [duplicate]

Recently I came across this article. http://www.cs.tau.ac.il/~tromer/acoustic/ Could this put all computers at risk for decryption?
4
votes
1answer
91 views

What is the private key in RSA?

I'm new to cryptography and I have a doubt: I read some pages a bit different definition for the RSA private key: In 1 - (n, d) In 2 - ...