Questions tagged [rsa]
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 with proper paddings.
2,784
questions
6
votes
4
answers
12k
views
Is it safer to encrypt twice with RSA?
I wonder if it's safer to encrypt a plain text with RSA twice than it is to encrypt it just once. It should make a big difference if you assume that the two private keys are different, and that the ...
6
votes
2
answers
5k
views
How to calculate the time it'll take to crack RSA or DH?
Sometimes the easiest way to describe security of a type of cryptography is to say that "the time it takes to solve for an x-bit key would be y years". How would one go about doing such a calculation ...
6
votes
1
answer
437
views
What is the reason for length differences in RSA?
In NIST FIPS 186-4, "digital signature algorithm", the minimal length allowed is 1024 bit (page 22). On the contrary, in NIST SP800-56B, page 63, RSA-OAEP encryption, the minimal length is 2048. Why ...
6
votes
1
answer
2k
views
Why use an RSA public key exponent of form $2^n+1$ instead of $2^n-1$?
The short exponents in RSA which are only a few bits in length,i.e. $e=3,\ 17$ and $2^{16} +1$
Why we are using exponents of the form ${}2^n+1$ not $2^n-1$?
6
votes
1
answer
558
views
Should different key pairs be used for signing and encryption?
In the recent iOS Security white paper from Apple (February 2014), the section on iMessage discusses using two different asymmetric key types as part of its standard operation:
When a user turns on ...
6
votes
1
answer
5k
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 ...
6
votes
2
answers
2k
views
Is RSA longer supported in TLS 1.3 and are RSA and DH fundamentally different?
I'm watching "SSL, TLS, HTTPS Explained" by ByteByteGo on YouTube and at the end, starting around 5:15, there are two points that are interesting:
in TLS 1.3 RSA is no longer supported as ...
6
votes
1
answer
490
views
Why can we not use the group $Z_{p}^{*}$ for cryptography?
Sorry if this is a noob question, but for instance in ECDSA, we start by considering the field $\mathbb F_p$, whose the elements also form a group under multiplication. Why don't we just use this ...
6
votes
2
answers
4k
views
Derive a secret from an RSA private key
What I want to do is deterministically derive a secure key from an RSA private key, such that the RSA private key cannot be derived from the secure key.
The first approach that came to mind was ...
6
votes
2
answers
266
views
Effect of $L_n[1/4,c]$ integer factorization on RSA-2048
Using the L-notation, integer factorization of an integer $n$ has the best known complexity of $L_n[1/3,c]$ using general number field sieve. Would discovery of an algorithm with complexity $L_n[1/4,c]...
6
votes
2
answers
2k
views
RSA cipher wrong use
Why is it foolish if you decide to use an RSA cipher to encode some message by first converting each letter of the message to an integer? So for exmaple Space=0, a=1, b=2,...
After the conversion I ...
6
votes
2
answers
354
views
RSA signatures without padding by using XOF output in range [1, n-1]
RSA signatures are implemented by encrypting the padded hash with the private key.
Why not take the approach RSA-KEM is using by removing the padding entirely and replacing the hash with a XOF that ...
6
votes
1
answer
3k
views
Risks of Using SHA1 Instead of SHA256 for RSA with OAEP Padding
I'm presently implementing a simple RSA-based encryption as follows in PHP (using openssl_public_encrypt):
...
6
votes
1
answer
544
views
Difference RSA keypair creation openSSL and openPGP?
Creating a 2048bits RSA keypair I figured that doing this using
openssl takes as an input 32bytes of "randomness" from ...
6
votes
2
answers
2k
views
RSA Signature Weak Padding Attack
Assume that we have a message $m$ of size $n$, and it is padded with two 01 bytes in front. Then the signature $s$ is computed using a private key $ks$. Can we ...
6
votes
1
answer
12k
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 a ...
6
votes
1
answer
364
views
RSA with 3e≡1 (mod p−1) and 5e≡1 (mod q−1)
Consider RSA with $p$ and $q$ large distinct secret safe primes in interval $\bigl(2^{(n-1)/2},\,2^{n/2}\bigr)$, and private key $(N,e,d,p,q,d_p,d_q,q_\text{inv})$ computed as
$$\begin{align}
N&=p\...
6
votes
1
answer
172
views
Difficulty of computing RSA keypair with given bits preset
Given a 2048-bit RSA public key physically burned into hardware, is it feasible to find a keypair where the public key could be "overlaid"? To detail, each bit in the hardware key is write-...
6
votes
3
answers
2k
views
Is it possible to check if a number is the product of two primes without factorizing it?
I have a large number which I suspect may be a private RSA key (although its size, at 613 bits, seems a bit unorthodox).
I have started to run a factorization algorithm on it, and after a few hours ...
6
votes
1
answer
3k
views
RSA attack with continued fractions (Wieners attack)
I found an article on the internet about an RSA attack with continued fractions.
Given are the following numbers:
$n = 205320043521075746592613$
$e = 70760135995620281241019$
$\frac{e}{n}=[0;2,1,...
6
votes
1
answer
766
views
Advantages of RSA / EC against QC attacks
We know that both the RSA and ECC algorithms are vulnerable against attacks using (future) Quantum Computing (QC). Are there however any advantages of choosing one algorithm over the other?
As an ...
6
votes
1
answer
7k
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?
6
votes
1
answer
5k
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?
6
votes
1
answer
759
views
Can RSA-PSS signing be made deterministic without loss of security?
Is it possible to make RSA-PSS signing deterministic without loss of security?
Specifically, I would use Blake2b of the key and message to generate the salt.
6
votes
1
answer
2k
views
Modular exponentiation on calculator for textbook RSA
How do you encrypt $51$ with public key $(n,e) = (91,23)$
I understand that $c = 51^{23} \bmod 91$. How can I calculate the result on a calculator?
6
votes
1
answer
5k
views
Recommended password complexity for SSH key encryption using AES-256-CBC
When protecting SSH private keys with password-based encryption, what would be a good minimum password complexity+length standard to make cracking the password too difficult to be worthwhile anytime ...
6
votes
1
answer
27k
views
What is the difference between SHA256WITHRSA and SHA256WITHRSAENCRYPTION digest algorithms?
I installed djigzo on my android phone and I want to use it for smime mail.
I don't know the difference between choosing SHA256WITHRSA and ...
6
votes
1
answer
7k
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?
6
votes
1
answer
1k
views
How to find an element of high-order in an RSA group?
Is this even possible? The RSA group is not cyclic, so usually you wouldn't find a generator for accessing all group elements.
What happens if you use the RSA group in a scenario where you want that ...
6
votes
2
answers
409
views
Why does OAEP have 2 rounds with 2 random oracles?
I strive into understanding why OAEP has two rounds of computations and not just one. I.e: Wouldn't it be safe to hash the random number r and XOR it with the original message?What security risks if ...
6
votes
2
answers
5k
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 ...
6
votes
3
answers
4k
views
How can I prevent a message replay with RSA?
I am using RSA to encrypt some data but I would like to eliminate the possibility of message replay. By message replay I mean sending a valid message multiple times to the original recipient. It is ...
6
votes
2
answers
1k
views
RSA with exponent being a factor of modulus
This weekend I participated in a CTF, but came across a task that I wasn't able to solve. I can't find any write-ups so I hope you can help me.
Given:
$$
n = pq\\
c_1\cong m_1^{\hspace{.3em}p} \mod n\\...
6
votes
1
answer
6k
views
RSA-OAEP: How does it work?
I was looking at this image about OAEP:
..and was wondering what was happening here.
We have a data block DB which consists of:
...
6
votes
4
answers
4k
views
How do institutions like banks do RSA with big primes?
When encrypting with RSA it is often infeasible to decrypt by just doing c^d mod n, because for example when using the primes $(p,q)=(12553,1233)$, which are small ...
6
votes
1
answer
757
views
Public-key authentication that is feasible by hand, before computers?
I wonder if it's possible to do public key authentication (preferably not vulnerable to replay attacks) before modern computers became a thing (e.g. in a medieval setting).
Specifically:
...
6
votes
1
answer
584
views
How fast is Factorization reduced to a Discrete Logarithm?
Given a RSA modulus $n$, which is the product of two safe primes:
\begin{align*}
P &= 2p + 1 \quad\quad\quad
Q = 2q + 1 \\
n &= P \cdot Q = 4p q + 2 p + 2 q + 1
\end{align*}
The ...
6
votes
2
answers
2k
views
Which elements of private RSA file are really constitutive of private key?
I have used openssl rsa to generate a RSA key of 2048 bits and as expected output belongs to a file beginning with ...
6
votes
1
answer
4k
views
Multiple private keys with RSA
Say I want generate pair of public/private keys. First of all lets choose two prime numbers $q = 17, p = 11$. Now, lets choose public key $e=7$ and try to determine the matching private key $d$:
$$d\...
6
votes
2
answers
2k
views
Trapdoor and RSA (Schneier)
Disclaimer: I'm new to cryptography.
Background: From Applied Cryptography (Bruce Schneier), page 30 of 2nd edition
A trapdoor one-way function is a special type of one-way function, one with a ...
6
votes
1
answer
368
views
Understanding Genkin-Pipman-Tromer's ground potential, side channel attack on RSA
I'm pretty sure that by now folks might have come across this research from Genkin-Pipman-Tromer (GPT) on extracting the RSA key used by GnuPG (GPG) just by measuring the ground potential. I'm going ...
6
votes
1
answer
1k
views
Question about why RSA is hard to attack
I think I understand why RSA is hard to attack but I'd like to get clarification if I actually do.
Assume there are two people, Alice and Bob, who are attempting to communicate privately but that we ...
6
votes
1
answer
404
views
How are trapdoor functions developed/found and where can I find existing ones?
Trapdoor functions are a fundamental part of public key cryptography. An example of the most common trapdoor is
Prime Factorization, used in cryptosystems such as RSA
How are these trapdoor ...
6
votes
3
answers
1k
views
Using an RSA private key simultanously as an AES encryption key to generate random numbers?
Currently I'm implementing a PRNG for an embedded system. Using the RFC 4086 I've decided to use the X9.17 - to be more specific the successor X9.31- standard to implement my PRNG. X9.17 uses DES, but ...
6
votes
1
answer
109
views
Finding the period of a function with a single output qubit - impact on RSA
In this paper,May and Schlieper claim that one can find the period of a function $f()$ by embedding $h \circ f = h(f(x))$ for input $x$. This would have the immediate consequence of reducing the ...
6
votes
1
answer
1k
views
RSA PSS security advantage
To my humble opinion, please correct me if I'm wrong, RSA-PSS (PKCS#1 ver 2.1) advantage over RSA as described in PKCS#1 ver. 1.5 is in its security proofs. Does this proof and the advantage is still ...
6
votes
1
answer
21k
views
RSA PKCS#1, v1.5 padding output
If I make use of RSA PKCS#1 in v1.5 what padding length is used. Basically, it is not allowed that the plaintext is bigger than the modulus. But what if the length in bits is the same (padding to ...
6
votes
1
answer
1k
views
Why don't use random padding in RSA?
Consider the following scenario:
Sender S sends a message to receiver R. He uses a hybrid encryption scheme with RSA as key-encapsulation algorithm and AES-256-CTR (4byte-counter) and SHA256-HMAC. ...
6
votes
1
answer
1k
views
Proof that padded RSA is CPA-secure
I'm referring to page 383 of J. Katz and Y. Lindell's Introduction to Modern Cryptography. The book presents a padded RSA:
${\bf Key Generation:}$ same as Textbook RSA (given security parameter $1^...
6
votes
1
answer
5k
views
Get RSA PlainText without Knowing Private Key
If I have an algorithm,RSA-Crack(), that, for a given RSA public key (n,e), is able to decrypt 1% of the messages encrypted with that key (without knowledge of the corresponding private key).Can there ...