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
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 ...
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: ...
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 ...
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 ...
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 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 ...
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....
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)...
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 \...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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. ...
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 ...
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 ...
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: ...
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

1
2 3 4 5
54