Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
378 views

How to find the public key in RSA?

Finding the public key given the private key $d$ and the prime numbers $p$ and $q$. $$p = 3092551601$$ $$q = 3490383433$$ $$d = 10719928016004921607$$ Since this is RSA, here is my thinking. In ...
1
vote
0answers
53 views

PKI Challenge Response: why is $h(r) = x$ enough to protect against chosen text attacks?

I think the question was asked somewhere else but not answered very precisely. Quoting from the "Handbook of applied cryptography": Identification based on PK decryption and witness. Consider ...
1
vote
1answer
260 views

Exploit RSA , given some information about n

Every week Bob updates his public RSA modulus $n=p*q$ and encryption exponent $e$ by picking a new pair of primes $p$ and $q$ and a new exponent $e$. After several weeks, bob becomes lazy and ...
8
votes
2answers
2k views

RSA: What would happen if you chose n to be a prime? [duplicate]

If Alice were to choose n to be a prime, instead of the product of two primes, what exactly would go wrong in the RSA cryptosystem? How would Bob decrypt her message?
3
votes
3answers
104 views

RSA public key same across all clients or different?

I understand that public key is a pair of $(e, N)$ where $N$ is product of two primes and $e$ is encryption key. I understand that $N$ is usually unique for an entity. For example, Facebook, Google, ...
3
votes
1answer
146 views

Understanding how Oscar can decrypt a message in RSA

I have the following set-up: Bob has an RSA Cryptosystem with a large modulus $n$ for which the factorization cannot be found in a reasonable amount of time. Alice sends a message to Bob by ...
1
vote
2answers
416 views

Paillier VS RSA

I was wondering if there are major pros or cons of choosing the Paillier algorithm over RSA except for Pailliers being additively homomorphic and RSA multiplicative?
0
votes
0answers
55 views

RSA - Half information

I have to solve this RSA exercise, I have $e, n$, the first part of $p$ and the last part of $q$. Any idea how I can solve it? $e=65537$ $n= ...
0
votes
2answers
61 views

RSA: Given two very large prime $p,q$ and $n=p\;q$, how to quickly find $e$ such that $\gcd(\varphi(n),e)=1$?

I can imagine that finding $p,q,n$ are easy, but my text book also says the $e$ can be found rapidly, so how does modern RSA find this $e$?
0
votes
0answers
52 views

Finding $d$ in RSA Encryption mathematically and by hand

I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically. Let's say $p=11$, $q=13$ $$N=p \cdot q=11 \cdot 13=143$$ I chose $e$ to be relatively ...
1
vote
1answer
292 views

Decrypting a message encrypted twice with RSA but with same n

A file has been encrypted with the same public key twice, in an effort to improve security. However, both n's are the same, only differing by the value of ...
0
votes
0answers
171 views

Understanding how to use RSA and AES in S/MIME

I'm sorry if the question is dense, my understanding of this topic is not thorough. I have to send an email adhering to: Encrypting the email message via AES-256 Encrypting the email with their ...
4
votes
1answer
616 views

Understanding WannaCrypt's hybrid encryption scheme

I'm confused about how WannaCrypt's hybrid encryption scheme works after watching Computerphile's "How WannaCrypt Encrypt's Your Files" video a number times. Below is my thought process to make it ...
2
votes
1answer
203 views

Factoring RSA-129 with a personal computer today

I have read the history of the RSA-129 challenge, and now I would like to know if it would be possible to factor RSA-129 with a single "average" personal computer, today. Has someone tried to do this ...
4
votes
1answer
147 views

How rare are 1024-bit $B$-smooth numbers?

What is the probability that if I choose a random $1 < r < n - 1$, $r^{65537} \pmod n$ will be $B$-smooth? $n$ is a 1024-bit RSA modulus. The Wikipedia pages on smooth numbers and the Dickman ...
0
votes
1answer
123 views

RSA private key?

I recently solved a stage in a challenge where I received 5 very large integers with character labels. I think they are components of an RSA key but I am a nooby to crypto and not sure. I have ...
0
votes
1answer
36 views

relationship between equivalent ways of computing RSA private key

I have found two ways to compute the RSA private key, but i have trouble understanding why they are equivalent. $1) D={k \phi(N)+1 \over E}$ $2) E* D=1 \mod \phi(N)$ $1)$ AFAIK comes from taking ...
3
votes
1answer
161 views

difference between the math of RSA problem and DH problem

I'm trying to understand why the RSA problem is not related to the Discrete Log problem, and how breaking the Discrete Log problem does not directly compromise RSA. I will explain my reasoning of why ...
3
votes
1answer
183 views

Is there a lower cost cryptography than elliptic-curves based cryptography?

ECC requires less CPU power, less memory and shorter keys than RSA or any other asymmetric cryptography I came across in the literature (correct me if I am wrong). Is there a lower cost asymmetric ...
1
vote
1answer
383 views

Finding the first few digits of p and q

Is there a way to find out the first few digits of the factors of the RSA numbers (RSA-1024 or RSA-2048)? I do not want to get all the digits but only first 4-5 digits. My question is thus more ...
5
votes
1answer
429 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,...
0
votes
2answers
127 views

Why does my attempt at RSA break?

I have that $N = 798$, $p=2$, and $q=399$. I choose $e$ such that $\gcd(e,(p-1)(q-1))=1$ where $e=7$. I, then, choose $m = 123$. Thus, $c=123^{7}\bmod798=669$, which is my ciphertext. After, I try $d=...
0
votes
1answer
533 views

How does RSA public and private key structure look like?

So I was reading this wiki about the RSA algorithm and I read this article to understand it better. My goal was to create a simple program that would generate private and public keys. I got to the ...
0
votes
0answers
17 views

In RSA, how can we observe the message with given two co-prime public keys and same n value? [duplicate]

I am not sure if the title is clear enough. Here is question's body: Alice and Bob are very good friends and they share the same RSA modulus n. Of course, to have their own different public keys, ...
0
votes
1answer
59 views

RSA and its Limitations [closed]

How and why do we face a problem when encrypting values of 0 and 1 using the RSA cryptography Algorithm? Is there any way to solve it?
4
votes
1answer
129 views

Weaknesses in vanity PGP keys

The program Scallion can generate vanity PGP keys and .onion addresses using the following method: Generate RSA key using OpenSSL on the CPU Send the key to the GPU Increase the key's public ...
0
votes
1answer
65 views

What is the totient function for an RSA modulus has several factors due to incorrect setup?

$ϕ(n)=p.q−(p+q)+1$ where there are two factor $p$ and $q$, but what if there were 3 (or more) factors such as $(p,q,r)$ due to a typo in specifying the modulus?
2
votes
3answers
253 views

Which is better when the secret is leaked, RSA or Diffie-Hellman?

I know that DH can be used for perfect forward secrecy but for the sake of this example, let's say that RSA and Diffie-Hellman are both used to establish a symmetric key that will be used for future ...
3
votes
1answer
116 views

Biased RSA moduli and ROCA

Say I can generate many 1024-bit RSA public keys $(N,e)$ with fixed public exponent $e = 65537$. They turn out to be heavily biased when computing $N \bmod x$ for small primes $x$. These congruences ...
1
vote
1answer
1k views

Breaking RSA using Chinese Remainder Theorem

When the same message is encrypted for three people who happen to have same public key but different values of n, it is possible to get the value of message by using Chinese Remainder Theorem. ...
0
votes
1answer
301 views

What role does RSA play in DHE_RSA cipher suite?

I've read in this article, that encrypting a premaster key with a RSA public key is not safe from forward secrecy attacks. If an adversary, records all communication between a client and a server. And ...
2
votes
0answers
286 views

RSA signatures that allow hash to move around in block

I'm looking at a broken RSA signature padding implementation in a real device. It's a very-badly implemented version of PKCS #1-like encoding, but before PKCS added the DER-encoded hash identifier. ...
2
votes
1answer
97 views

Keyspace of asymmetric ciphers. (RSA)

I have difficulty finding information about key space calculation of RSA. I think there is a gap in my math knowledge that prevents me from understanding the problem. I know that symmetric ciphers ...
2
votes
1answer
207 views

NIST vectors for RSA 4K Key

Please suggest the link where I can find out the NIST vectors for 4K Key to test my RSA API.
3
votes
0answers
51 views

Does secure LWE implementation leak bit information?

We know RSA leaks one bit about the factors and improper yet secure implementations of Discrete Logarithm leak one bit about the discrete logarithm. Does LWE leak any information?
-2
votes
1answer
176 views

Why do RSA public keys begin with 3048024100?

RSA public keys seem to begin with 3048024100, why? They also seem to end with 0203010001
1
vote
3answers
145 views

Explaining RSA to non-scientists

I am to give a small lecture on quantum computing in a months' time and I want to shortly give an intuition to the fact that Shor's algorithm shows that quantum computers will break RSA. Ideally, I ...
3
votes
1answer
119 views

Does an adversary require the public key to perform operations when RSA or ECC is broken?

If we had a way to break signature or encryption schemes (e.g. recover the key, recover plaintexts from ciphertexts, forge signatures), e.g. a quantum computer that was powerful enough to break ...
3
votes
0answers
230 views

How to determine the correct padding to use for rsa signing?

Before today I didn't know the difference between RSA padding for encryption and for signing, I think this answer describes it pretty succinctly, however, I don't know if there is an optimal padding ...
-1
votes
1answer
388 views

about rsa decryption with given n,e,2d+phi(n)

I have given n, e, c, and 2d+phi(n). any idea how to proceed to solve that RSA. for values click on this:- https://pastebin.com/mdeSdfzD
3
votes
2answers
326 views

Given one message encrypted repeatedly with the same 'n' but different 'e's, is it possible to decrypt the ciphertext without simply bruteforcing n?

I'm trying to solve a problem where I've been provided with a few public keys and the ciphertext, and I've been told that the plaintext was encrypted repeatedly using all of these keys. However, all ...
0
votes
0answers
45 views

Compare two asymmetric encrypted strings?

I am new in cryptography. I just want to compare two asymmetric encrypted strings. For that I need the same encrypted string for the same text, is this possible with asymmetric algorithms? Right now ...
-1
votes
1answer
109 views

Integer Factorisation

If I have a set of numbers of the form $\{ {kp+r}:k\geq0\}$ with p a prime or product of primes k large in $\in Z^+$ and r fixed, is it computationally feasible to find a factorisation for any one ...
0
votes
1answer
82 views
5
votes
2answers
1k views

Why is Diffie Hellman used alongside public keys?

I just read this post here: Why do we need asymmetric algorithms for key exchange? that asserts that in public key cryptography when asymmetric keys are used to secure communications, for parties to ...
1
vote
0answers
48 views

How the SW layer communicates with TPM?

In a system with TPM, an RSA private key is kept secretly by the TPM and no one can access it. When something needs to be decrypted using this key, does the TPM itself decrypt the whole massage? How ...
0
votes
2answers
58 views

How can a decryption program tell me that a private key is incorrect for RSA and ECC?

I have a program which will encrypt the symmetric key with RSA public key with keysize 2048. I am able to decrypt the message with the corresponding private key. My question is, is it possible to ...
1
vote
2answers
93 views

Distinguish between cipher-texts of text-book RSA and RSA/OAEP

Is there is a possibility to identify from cipher-text that, this is been encrypted using a text-book RSA or RSA with OAEP padding. (By looking at the cipher-text only) ?
12
votes
0answers
140 views

Fewest qubits required for the discrete logarithm problem and integer factorization

According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
0
votes
1answer
183 views

Group signatures, security and ECDSA

I am reading up on group signatures. With RSA a public key can have more than one private key. For a public exponent $e$, private exponent $d$ and modulus $n$, there is more than one solution for the ...