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,663
questions
0
votes
0
answers
21
views
Does the article "Factoring integers with sublinear resources on a superconducting quantum processor" affect ECC? [duplicate]
"Factoring integers with sublinear resources on a superconducting quantum processor" seems to indicate the end is getting closer for RSA - much faster than anticipated earlier:
We proceed ...
- 331
3
votes
1
answer
41
views
Cost of attacking textbook RSA signature of $b$-bit hash of the message
A signature system applies textbook RSA to a $b$-bit hash of the message. What's the cost (preferably, as CPU time on common hardware) of existential forgery assuming known signature of $r$ random ...
- 132k
0
votes
0
answers
49
views
RSA decryption given C (Cipher Text), e, and d [duplicate]
I am given C, e, and d to decode an RSA ciphertext (or would it be SRA given this information?), and I am thoroughly confused. I have tried working backward to n by reversing modulo operators and then ...
0
votes
0
answers
33
views
Security implications of leaking d, e, and a ciphertext in an RSA calculation? [duplicate]
I'm learning about RSA, and one of the textbooks I'm studying from talks about the security implications of various parts of an RSA key pair being leaked. It talks about what happens when an attacker ...
1
vote
0
answers
46
views
Which cryptographic attack here is feasible on RSA? [duplicate]
I'm new to cryptography, so please don't bash me.
I'm trying to learn to recover a RSA private key. As you can see from my profile I'm a cybersecurity professional, which is only now trying to learn ...
- 123
2
votes
1
answer
350
views
Crack RSA with $e$ and $d$?
Is it possible to decipher a ciphertext, in RSA with small primes (two 128-bit factors) when we only have ciphertext $c$, private exponent $d$ and public exponent $e=65537$ to crack it? I try hard on ...
- 121
0
votes
0
answers
16
views
In Python RSA broadcast attack, why am I using bit length in this binary search for the cube root? [migrated]
https://stackoverflow.com/a/23622115/9481613
Shows this function:
...
- 101
1
vote
0
answers
44
views
RSA: decipher c when everything except N is known [duplicate]
Is it possible to solve this:
If you have the following information about an RSA ecrypted plaintext $m$:
$e = 65537$
$d$, $c$ some very large numbers
$p$ and $q$ are both random 128-bit long prime ...
- 111
1
vote
1
answer
81
views
Textbook RSA security for fully random message
I am asking this since I can't find definite answer.
Is it secure if I use textbook RSA provided all my data is 2048 bits ( or any N <=2048 for 2048 bit key ) and it is random ( using Secure Random ...
- 11
1
vote
1
answer
26
views
NIZK Proof of Knowledge of a Standard RSA Signature on a message (without signer participation)
I'm looking for a protocol in which a Prover transforms a RSA signature $\sigma$ on a message $m$ that verifies under a public key $vk$ into a NIZK proof of knowledge, $\pi$ of that signature. A ...
- 2,236
0
votes
0
answers
201
views
RSA : Is there a way to compute phi(n) or N itself if we only know e, d and a ciphertext?
I am trying to solve a problem where private key exponent d, ciphertext c, and public key exponent e (65537) are known.
How can I calculate φ(n) or n itself?
An extended version of the problem would ...
- 13
3
votes
1
answer
69
views
What is the modern terminology for a digital signature scheme with a shadow?
In Guillou and Quisquater's 1988 paper "A 'Paradoxical' Indentity-Based Signature Scheme Resulting from Zero-Knowledge", they say that an RSA identity has a shadow and go on to state that ...
- 2,236
2
votes
1
answer
67
views
Why is $d = e^{-1} \mod \phi(N) \equiv e^{\phi(N)-1} \mod \phi(N)$ and not commonly used in RSA key generation?
On some lecture slides regarding to RSA-Encryption, the formula for calculation of the private key is given as $d = e^{-1} \equiv e^{\phi(N)-1} \mod \phi(N)$. The second equation is justified by the ...
- 21
0
votes
1
answer
80
views
How does the public key cryptography algorithm generate a public key based on the private key? [closed]
Because of the need of the project, I want to develop a simple public key cryptography algorithm, but I have doubts when generating the key pair.
I have learned about the key generation process of RSA....
- 29
3
votes
1
answer
230
views
Time Complexity of RSA Trial Division
I'm having trouble understanding how time complexity of trial division is exponential.
If it takes $\sqrt n$ tries to factor $n$ in the worst case scenario then time complexity is $\mathcal{O}(\sqrt n)...
- 33
1
vote
0
answers
62
views
What is the proof that the RSA is collision-free?
We have the RSA function:
$c = m^e (mod n)$.
I would like to know the proof that there is not an $m_1$ and an $m_2$ message that produce the same $c$.
My thoughts:
We know that $m \le n$, so $m_1 \...
- 11
1
vote
0
answers
23
views
Single Term Off-Line Coins : Corrections on the final signatures
I am making an implementation of Niels Ferguson's paper: Single Term Off-Line Coins in Python.
In the Coin withdrawal protocol, in the last steps, Alice checks that the signatures she received are ...
- 33
-1
votes
0
answers
27
views
RSA Decryption using N without Factorization [duplicate]
So the problem is this Alice decides to use RSA with the public key $N$ = 1889570071. In order to
guard against transmission errors, Alice has Bob encrypt his message twice, once
using the encryption ...
7
votes
3
answers
7k
views
Can Quantum Computers crack RSA and AES?
Im trying to learn more about cryptography and ran into a post, Is AES-128 quantum safe?, which asks if AES-128 is safe. From the articles and replies it seems that AES-128 (symmetric key) is safe ...
1
vote
0
answers
40
views
Can $s$ be any number in $s^x = x \bmod N$, where $N = p \cdot q$ for de Jonge / Chaum?
I was reading about some way to imagine the signature of a message using the RSA problem :
Let $N$ be the product of two prime numbers $p$ and $q$. Let $s$ be
the signature of a message $s$ (provided ...
- 11
0
votes
1
answer
84
views
Would it be technically possible to use hundreds of computer processors together to work on an algorithm like the Shor's algorithm and break RSA?
Would it be technically possible to use hundreds of computer processors together to work on an algorithm like the Shor's algorithm and break RSA?
I've been reading about the crazy amount of qubits ...
- 9
1
vote
0
answers
59
views
Recovering multiple of $\phi(N)$ given two private public key pair
Assume $\phi(N) = (p - 1) (q - 1)$ as in the original paper. Suppose that we are using the same modulus $N$ for public and private key pairs $(e_1, d_1)$ and $(e_2, d_2)$. How can we get a multiple of ...
- 11
7
votes
2
answers
500
views
Why does RSASSA-PSS rely on full collision resistance whereas RSA-PSS only relies on target collision resistance?
This is sort-of a reply to the top answer given to this question, which states that whereas RSA-PSS, defined in terms of $H(r \ || \ M)$, only relies on target collision resistance and is secure even ...
- 103
2
votes
1
answer
82
views
Is there a CRHF based on integer factorization problem or RSA assumption
We know that in the black-box sense, we cannot use one-way functions to construct Collision Resistant Hash Functions.I feel that in my impression, I have never seen CRHF based on integer factorization ...
- 105
1
vote
3
answers
126
views
Why can't we just increase the bit length to counteract shor's algorithm?
I know that it sounds like a very stupid question but if Shor's algorithm has a complexity of roughly $n^3$ why cant we just increase the bit size until the time for the algorithm to run is ...
2
votes
1
answer
106
views
Application firmware sign-then-encrypt vs encrypt-then-sign
I know that there are previous questions on the subject e.g. here, however I would like to ask it for my particular (simple) case.
I have an application firmware that is downloaded to a microprocessor ...
- 137
1
vote
0
answers
56
views
RSA Key Generation & encrypted output using OpenSSL
When is it generally acceptable, if ever, to generate RSA keys without encrypting the PEM output with another encryption algorithm?
I am working on a CI/CD process and want to leverage asymmetric ...
- 11
1
vote
1
answer
79
views
Non probabilistic algorithm : Given secret key $d$ we can factorize $n$ assuming $e$ is small
I read in an introduction to a paper that if $e$ is small enough and we were given secret key $d$ in RSA, then there is an efficient deterministic algorithm to factorize $n$. I've searched about that ...
- 173
2
votes
1
answer
70
views
Iteration count for (enhanced) Miller-Rabin
In FIPS 186-5 (Digital Signature Standard or DSS) there is a Table B.1 which specifies the minimum number of rounds of Miller-Rabin testing for 1024, 1536 and 2048 bit keys, used for digital ...
- 89.3k
-2
votes
1
answer
60
views
Can someone please explain RSA-OAEP in plain english mathematically?
RSA mathematics: https://youtu.be/4zahvcJ9glg
I understand how RSA works mathematically.
Can someone explain RSA-OAEP in plain english?
- 25
2
votes
1
answer
83
views
is this how RS256 works in JWT?
I'm a newbie that is studying about JWT using RS256 algorithm for signing and verification. I have drawn a diagram that represents my understanding of how RS256 works.
Basically, below is what I ...
- 121
2
votes
1
answer
46
views
exponent bit-length for hard DL (128-bit security)
Following up on my previous post, I thought I might get a more concrete answer if I gave a more concrete question.
I require 128-bit security so I choose a 3072-bit RSA modulus ($\ell_n=3072$). ...
0
votes
0
answers
44
views
Sharing encryption key via intermediary without the intermediary having access to the content
Please bear with me...
I want to store some data in an untrusted location (a server). I will want to share this with other people.
I encrypt the data with AES encryption and a 20 character password. ...
- 101
2
votes
1
answer
75
views
Hardness of DL in group of Quadratic Residues (product of safe primes)
A protocol I am working with requires $\ell_n$-bit RSA modulus and $\ell_\Lambda$ such that computing $\ell_\Lambda$-bit discrete logs is hard in $QR_n$ (technically $n$ is $\ell_n+2$ bits in the ...
5
votes
1
answer
131
views
RSA Key Pair Generation - limit on $e$
FIPS 186-4 and NIST SP800 56B states following limits for public exponent $e$
$e$: a pre-determined public exponent − an odd integer, such that $65,537 ≤ e < 2^{256}$.
What security issue arises ...
- 2,313
0
votes
1
answer
41
views
Maximum Security of RSA
Table 2 of NIST SP-800 56B provides Estimated Maximum Security Strength of different modulus sizes. It means that RSA-3072 provides security of 128-bits at Max.
Is it the case for symmetric algorithms ...
- 2,313
5
votes
3
answers
607
views
FIPS 186-4, Use of RSA key pair for Encryption and Signature
Section 5.1 of FIPS 186-4 states that
An RSA key
pair used for digital signatures shall only be used for one digital signature scheme (e.g., ANS X9.31, RSASSA-PKCS1 v1.5 or RSASSA-PSS)
and
RSA ...
- 2,313
1
vote
0
answers
37
views
Should I implement a key store / key management system into my python library? [closed]
I've created a python library that uses both RSA and AES encryption to allow for hybrid encryption of text or images. I am wondering if I should implement a keystore and/or a better key management ...
- 11
4
votes
1
answer
418
views
Security Strength of Symmetric vs Asymmetric Ciphers
NIST SP 800-57 Part 1 rev 5 section 5.6.1.1 gives following comparison between different encryption types. For example, it shows that 3TDEA, RSA-2048, ECC224 provides security strength of 112 bits.
...
- 2,313
1
vote
2
answers
157
views
Asymmetric encryption of transaction log file: is RSA the correct algorithm
I want to produce a transaction log that is encrypted while being produced. I'd prefer asymmetric encryption. It is possible that my program will terminate without writing any closing blocks, so my ...
- 113
1
vote
1
answer
101
views
Using roots of unity mod n to break rsa when e and phi are not coprime
I am trying to solve an rsa problem where we only know the public key (n,e) and the ciphertext c.
The modulus n is actually a prime number, so we can easily compute phi as phi = n-1.
But the problem ...
- 13
0
votes
1
answer
43
views
Curious about CCA attack for RSA, and Kerckhoffs's principle in general
I'm a student studying cybersecurity for the first time, and the part where our textbook explains using CCA attacks for RSAs seemed really unclear for me, so I am here seeking for clarification.
Our ...
3
votes
1
answer
85
views
How to decrypt c when e is not co-prime with phi(n) and e is non-prime
In RSA, I want to know a way to be able to retrieve all possible plaintexts $m$ given a ciphertext $c$, $\phi(n)$, $n$ and $e$. The decryption exponent $d$ can not be generated due to the fact that $e$...
- 31
1
vote
0
answers
23
views
For RSA keys, is there any security benefit to having P and Q of different bit counts [duplicate]
In some RSA libraries I've encountered, the P bit count is left shifted by some amount and Q bit count right shifted by the same amount. For example, if generating a 2048 bit key, the P bit count ...
- 217
0
votes
1
answer
74
views
How to decrypt a RSA plaintext given a public exponent e and a RSA modulus n
I am doing a RSA cryptography task where I need to decrypt a ciphertext but I am only given the ciphertext ,c, a public exponent, e, and a RSA modulus, n, which has two prime factors p and q such that ...
6
votes
1
answer
737
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:
...
- 63
7
votes
1
answer
388
views
RSA public keys such that encryption is identity
In this question, we restrict to RSA public keys $(n,e)$ such that
$n$ and $e$ are odd, $3\le e<e_\max$, $e<n$
Note: For some old Windows API, $e_\max=2^{32}$. In FIPS 186-4, $e_\max=2^{256}$. ...
- 132k
1
vote
0
answers
29
views
What are the possible CCA attacks on RSA with r||m+G(r) as the padding?
I was trying to come up with simple padding functions for the RSA, then trying to break them just to have a better understanding of why we need all the pieces used in the RSA OAEP... So, I am ...
1
vote
1
answer
107
views
In RSA, what if the message 'm' to be sent equals to one of the 2 prime numbers 'p' and 'q'?
In RSA, one of the math background is:
m ^ φ(n) % n == 1, where m is the message to be sent, ...
- 127
1
vote
1
answer
219
views
In RSA, how to calculate the private exponent 'd', after choosing 'e'?
Seems there are 2 ways:
d = (ϕ(n)*k + 1) / e
In this case, need to choose a proper integer k.
Question 1: How to choose k, just try positive integers start from 1, ...
- 127