Skip to main content

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.

Filter by
Sorted by
Tagged with
9 votes
3 answers
2k views

Does this RSA decryption scheme make sense?

A custom file format has a header encrypted with a 2048-bit RSA public key. I need to decrypt it using a 2048-bit RSA private key. The header has 48 bytes, and according to the scheme I got for the ...
Maksym Shcherban's user avatar
0 votes
0 answers
26 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 ...
Ole Tange's user avatar
  • 331
3 votes
1 answer
72 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 ...
fgrieu's user avatar
  • 142k
1 vote
0 answers
110 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 ...
Sir Muffington's user avatar
2 votes
1 answer
771 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 ...
Siyanew's user avatar
  • 121
1 vote
0 answers
46 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 ...
Beru's user avatar
  • 111
1 vote
1 answer
106 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 ...
Jakub Rogacz's user avatar
1 vote
1 answer
379 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 ...
Ethan Heilman's user avatar
0 votes
0 answers
339 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 ...
bd55's user avatar
  • 33
3 votes
1 answer
103 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 ...
Ethan Heilman's user avatar
2 votes
1 answer
229 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 ...
Mr. McNiki's user avatar
0 votes
1 answer
151 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....
SN-Grotesque's user avatar
3 votes
1 answer
344 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)...
ikeachairs's user avatar
1 vote
0 answers
94 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 \...
Jakab Martin's user avatar
6 votes
3 answers
9k 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 ...
cryptoman534345's user avatar
1 vote
0 answers
43 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 ...
Satochi's user avatar
  • 11
0 votes
1 answer
104 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 ...
Yuniel G's user avatar
1 vote
0 answers
112 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 ...
BBForage's user avatar
7 votes
2 answers
660 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 ...
whatf0xx's user avatar
  • 203
2 votes
1 answer
131 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 ...
constantine's user avatar
1 vote
3 answers
181 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 ...
HarryFoster1812's user avatar
2 votes
1 answer
304 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 ...
Fabius Wiesner's user avatar
1 vote
0 answers
237 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 ...
Johnny Bass's user avatar
1 vote
1 answer
96 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 ...
tonythestark's user avatar
2 votes
1 answer
174 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 ...
Maarten Bodewes's user avatar
  • 93.2k
-2 votes
1 answer
215 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?
mee's user avatar
  • 25
2 votes
1 answer
2k 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 ...
William Le's user avatar
2 votes
1 answer
55 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$). ...
gormatron3000's user avatar
0 votes
0 answers
49 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. ...
amlwwalker's user avatar
2 votes
1 answer
99 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 ...
gormatron3000's user avatar
5 votes
1 answer
194 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 ...
crypt's user avatar
  • 2,449
0 votes
1 answer
86 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 ...
crypt's user avatar
  • 2,449
5 votes
3 answers
752 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 ...
crypt's user avatar
  • 2,449
1 vote
0 answers
144 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 ...
Vey's user avatar
  • 11
4 votes
1 answer
590 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. ...
crypt's user avatar
  • 2,449
1 vote
2 answers
246 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 ...
Joseph Larson's user avatar
1 vote
1 answer
270 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 ...
bd55's user avatar
  • 33
0 votes
1 answer
123 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 ...
Green Ideology's user avatar
3 votes
1 answer
796 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$...
zerver's user avatar
  • 31
1 vote
0 answers
24 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 ...
ubiquibacon's user avatar
0 votes
1 answer
497 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 ...
user106260's user avatar
6 votes
1 answer
761 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: ...
Azuresonance's user avatar
7 votes
1 answer
404 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}$. ...
fgrieu's user avatar
  • 142k
1 vote
0 answers
54 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 ...
Hilder Vitor Lima Pereira's user avatar
1 vote
1 answer
188 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, ...
Eric's user avatar
  • 137
2 votes
1 answer
7k 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, ...
Eric's user avatar
  • 137
0 votes
2 answers
126 views

Will the value of the "version" fields always be 0 and the "NULL" fields always be "NULL" in PKCS#1, PKCS#8, and X.509/SPKI keys?

Consider the fields highlighted in red in the following keys. Will the "version" fields (i.e. INTEGER 0) always be zero for the specified structure? Will ...
ubiquibacon's user avatar
3 votes
1 answer
176 views

RSA signature verification: How is the "integer too large" error in RSASSA-PKCS1-V1_5-VERIFY possible?

Step 2 of the PKCS #1 v1.5 signature verification operation as described in RFC 8017 section 8.2.2 reads: ...
edsq's user avatar
  • 33
0 votes
0 answers
29 views

What PKCS standard is this? [duplicate]

What PKCS standard is the public key in the image below? It seems to me that it is PKCS#8, but what I've read makes me think that PKCS#8 only applies to private keys. Here is the corresponding ...
ubiquibacon's user avatar
3 votes
1 answer
8k views

Confusion over PKCS#1 and "traditional" options with OpenSSL

I'm attempting to generate a private/public key pair in a few different standards and formats for testing an encryption library I'm working on (i.e. keys with the same "guts", but different ...
ubiquibacon's user avatar

1 2 3
4
5
57