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,831
questions
1
vote
1answer
61 views
Can the RSA accumulator scheme be converted to Elliptic Curve math?
Is it possible to translate the RSA accumulator scheme directly to EC without requiring bilinear pairings?
In RSA we have:
$A_{n+1} = A_n^c$ st. $\{c \: \textrm{prime} \: | \: c \in [\...
-1
votes
3answers
51 views
-2
votes
0answers
50 views
Differences between Gcd and factoring [on hold]
please can someone explain to me the difference between the following. Using two different numbers I. E one is the rsa key and the other a number working from 2 upwards to work out the Gcd, until the ...
1
vote
1answer
68 views
Value of $\varphi(n)$ and $\lambda(n)$
Is it true that $\varphi(n)$ is generally larger than $\lambda(n)$ for the same $n$? If so, can anyone give me a proof?
25
votes
5answers
15k views
Why does RSA need p and q to be prime numbers?
Despite having read What makes RSA secure by using prime numbers?, I seek a clarification because I am still struggling to really grasp the underlying concepts of RSA.
Specifically, why can't we ...
3
votes
1answer
770 views
Can a public key be same as private key?
As I understand, we choose the public and private keys to be mutual inverses. However, it is possible that, in a group, there can be numbers which are their own inverses.
E.g. Consider p = 7, q = 3. n ...
-1
votes
0answers
56 views
How to find prime number q in RSA?
To be assumed in RSA key generation algorithm $p$ is a constant prime number and $e$ is an arbitrary prime and also $d$ is an odd number that is relatively prime to $e$.
Based on these conditions ...
1
vote
1answer
52 views
Computational Complexity: ECC multiplication vs Modular multiplication
How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime?
I.e. on a given elliptic curve of size $|t|$, what's the complexity ...
0
votes
1answer
34 views
Factorization of the public value $N$ from the RSA cryptosystem
It is mentioned here that the public value $N=p*q$ of the RSA cryptosystem can be factorized if one of the factors is reused. Thus, if $N_1=p*q_1$ and $N_2=p*q_2$ and only $N_1$ and $N_2$ are known, ...
11
votes
2answers
13k views
Using ECB as RSA encryption mode when encrypted messages are unique?
As I understand, ECB should not be used as encryption mode unless you are encrypting single blocks of data which are always unique and only are encrypted once.
I have a collection of ids represented ...
1
vote
0answers
52 views
Fermat's little theorem in RSA with CRT
I have a question about the calculation of RSA decryption with the help of the CRT (Chinese Remainder Theorem).
If $c$ is the crytogram, $m$ the message, $d$ the private key and $p, q$ the primes.
...
2
votes
2answers
539 views
Why does adding PKCS#1 v1.5 padding make RSA encryption non-deterministic?
I'm quite a beginner to cryptography, but have been implementing some encryption according to a specification over the last few weeks using the PyCrypto library.
I've discovered that when encrypting ...
0
votes
1answer
103 views
Could a quantum computer recover files from ransomware if the attacker doubly encrypted them with RSA-4096?
How would a quantum computer decrypt a file (or find the keys to such a file) if it were encrypted with standard RSA 4096 encryption, but encrypted two times with different keys? The keys are known by ...
1
vote
3answers
126 views
How does AWS Secret key and access key work
Those keys are too short to be public/private RSA keys. What are they? How does it use them to authenticate the client?
My guess is:
AWS access key ID is a form of unique user/account identifier
AWS ...
101
votes
7answers
61k views
How big an RSA key is considered secure today?
I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the ...
0
votes
1answer
65 views
Can we estimate the amount of entropy required to generate an RSA key?
Of say 4096 bits as is a default GPG master key.
I can manage the first one or so almost immediately on Ubuntu. It then runs out of entropy when generating several more RSA keys, and I'm forced ...
-4
votes
0answers
29 views
Which company use RSA, ElGamal, DSA, ECDSA digital signature [on hold]
I need a list of companies, for example in my BSc, that use one of those digital signatures:
RSA digital signature,
ElGamal digital signature,
DSA digital signature,
ECDSA digital signature.
0
votes
1answer
106 views
Why RSA2048 sign of Intel accelerate card is fast?
Intel accelerate card
This card executes rsa2048 sign 35K ops(operation/second). My fast version is only 100 ops.
I can't find any HSM paper that has same performance level.
I am interested in this ...
-2
votes
1answer
93 views
Are there any flaws in this pseudocode?
I'm developing an algorithm that cracks small RSA keys (And theoretically bigg ones too, though might take some time), and was wondering if anyone you spot any flaws in this python code:
...
4
votes
3answers
808 views
Is it possible that two distinct RSA moduli share both of their prime factors?
I am using an algorithm (can be found here1) that can compute efficiently the GCD of multiple RSA keys. It intended for RSA keys that were generated with low entropy and may have one of their primes ...
3
votes
1answer
1k views
In which public key encryption algorithms are the private and public key not reversible?
The RSA public key encryption system has the characteristic that the public key and the private key can be reversed. That is, information encrypted with the public key can be decrypted with the ...
0
votes
0answers
43 views
Encryption/Decryption on multiple users using RSA?
Supposing I have Alice that is the RA, Bob (who is a user) and Kate (who is also a user). For now I use RSA. Alice sends a message to Bob. Alice also sends a message to Kate. Bob and Kate exchange ...
0
votes
0answers
29 views
Alternate to distributing master key to every user in circle of trust
I am designing an end-to-end encrypted file storage system where only the user should be able to access their own data. The best I could come up with is a system designed around a master key that is ...
9
votes
4answers
6k views
Why do we need Euler's totient function $\varphi(N)$ in RSA?
After we calculated $N = p * q$, we calculate $\varphi(N)$ and use it later to determine $e$ (PR) and $d$ (PU). But why?
For decryption and encryption we only use $N$ and don't need $\varphi(N)$. So ...
2
votes
1answer
66 views
Is there an equivalent to an RSA UFO in lattice-based cryptography?
So there's this concept within the realm of RSA cryptography called an RSA UFO. It is an extremely important function in the context of cryptocurrency. When starting up a cryptocurrency the creator(s) ...
1
vote
1answer
68 views
What encryption shoud I use for single char encryption?
I'm very new to encryption and I wanted to know if it is secure or just possible to use encryption on single chars. I did some research, but nothing to clear and i'm a bit confused.
The modes I think ...
2
votes
1answer
61 views
Can the original data be extracted from an RSA private key signed message
I'm working on a system that the main objective is to verify the message was written by the right person, but it would also be desirable if the message can't be understood by anyone sniffing it.
It ...
-4
votes
2answers
86 views
Prime number size and RSA decryption
Is there a former proof for why larger prime numbers make RSA securer? Maybe a theorem to show that it takes much more time to find out the private key if primes are larger?
3
votes
3answers
207 views
RSA - What's to stop someone from using the same ciphertext to mimic private key holder?
I've recently looked into fundamentals of RSA and think I understand how it works. However, there's one basic problem I can't seem to figure out. If someone received ciphertext for a given message, ...
0
votes
1answer
52 views
What does it imply if in RSA pow(m, e, n) is same as the m
So, Let's assume we have n which is made up of 2 strong primes which cannot be factored & e which is textbook value of e ...
0
votes
0answers
30 views
RSA Digital Signature System is failing for larger Prime numbers [migrated]
I implemented RSA cryptosystem to create a simple digital signature system. It is for freeCodeCamp's upcoming Cryptography curriculum.
The below program logs "Failure" when I use some bigger prime ...
0
votes
2answers
103 views
Why is prime number size important for RSA security?
RSA modulus is $N = pq$ where $p$ and $q$ are prime numbers. I read from somewhere that the time it takes to decrypt the RSA encryption increases exponentially as key length increases, which depends ...
7
votes
0answers
158 views
RSA factorization with special primes
Suppose that primes for RSA modulus are generated using formula:
$P_i(x,y) = \operatorname{next\_prime}(x^{z_i}+y^{z_i}) = x^{z_i}+y^{z_i}+d_i$
where $x,y$ are unknown random numbers with size 128 ...
0
votes
1answer
40 views
Probabilistic verification of signature schemes like RSA?
I was wondering if there were any verification algorithm in the literature that enables a "probabilistic" verification of well-known signature schemes?
For RSA signature verification for example, is ...
1
vote
1answer
44 views
I have created values for RSA encryption but it doesn't always work [duplicate]
I am using the values as follows:
$(p, q, n, \phi(n), e, d) = (1033, 5039, 5205287, 5199216, 65537, 3784241)$
Yes, I have made sure $e$ and $\phi(n)$ are coprime.
For example, if I were to encrypt ...
0
votes
1answer
78 views
Plain RSA with $3$ primes, find all integers $x$ so that $x$ is equal to $y$ when $y= e_K(x) = x^{b} \bmod n$
I'm using the notation from the book: Cryptography: Theory and Practice, Third Edition.
I have a cryptosystem with the following information:
$n = p_1 p_2 p_3$ and integer $x$ is encrypted using $y =...
2
votes
1answer
50 views
Brute forcing the value of m in RSA
I looked into the math behind RSA and seem to understand the basic encryption and decryption scheme.
Let's say there are two parties, Alice and Bob, who wish to communicate and secure their ...
2
votes
1answer
29 views
consequences of using fixed values with OAEP
With DSA / ECDSA using a fixed $k$ means the private key can be trivially easily calculated from two different signatures. To remedy this RFC6979 Deterministic Usage of the Digital Signature Algorithm ...
2
votes
1answer
93 views
man-in-the-middle attack on text-book RSA PKE
I am attempting to solve the following problem:
I know the following:
3 messages are being sent between Alice and Bob, all messages are encrypted with the known public key $(d,N)$:
Alice sends ...
11
votes
1answer
206 views
Is this paper's technique for factoring RSA 2048 with noisy qubits realistic?
A paper titled How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits has just come out which proposes a technique to factor RSA keys with moduli up to 2048 bits with a design ...
3
votes
1answer
106 views
What makes lattice-based cryptography quantum-resistant?
As opposed to RSA or elliptic curve cryptography?
1
vote
1answer
72 views
How should I address message size limits in RSA encryption?
I am making an end-to-end encryption software program in Java using RSA. I am using BigIntegers and its number theory methods. (I know this is a very slow approach, but I just want to learn to the ...
0
votes
0answers
45 views
RSA attack with really big N? [duplicate]
N is a really big number,2466 digits in base 10,and e is 65537,I thought n might be factored,but it didn't work. N is such a big number and e is 65537,smaller than N,so how to attack it?
3
votes
1answer
166 views
Inclusion and Exclusion proofs in RSA accumulators
I am reading about RSA accumulators from this video and few other sources. I had a confusion whether the complete set is needed to construct a proof of inclusion/exclusion in an RSA accumulator or is ...
-3
votes
1answer
72 views
how to decrypt if p=q in RSA [duplicate]
p,q should be different,but if I let p = q,and encrypt the plaintext,then I can't decrypt it,so can decrypt it?
1
vote
1answer
72 views
RSA - Very big Modulus and Ciphertext
Is there a known weakness in RSA when the value of modulus (n) is very large?
n = 2466 digits
e = 65537
c = 2466 digits
n cannot be factorized. I checked on ...
-1
votes
1answer
84 views
RSA encryption, Number theory [duplicate]
In RSA algorithm we have the value of $e$ & $d$ exponent and also one of the prime numbers. My question is how to produce another prime number that is not equal to the first one and the digit of a ...
-2
votes
1answer
35 views
Given a point $c$ in a field $Z_p$. Can we get another value $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$?
If we have a point in a field $c$. Can we get another value $c^{'}$ such that
$\left(c^{\prime}-c\right)$ is invertible in $Z_p$ ?
2
votes
2answers
97 views
Asymmetric keys (e.g. RSA) must be so much longer than symmetric keys (e.g. AES). Why? [duplicate]
I have been reading that RSA has to do with math (prime numbers), while symmetric key encryption deals with blocks of data and modifying the blocks with replacements and remappings, but I still don't ...
1
vote
2answers
56 views
Efficient attack on RSA with known padding scheme and public key
I am having some trouble with an assignment problem. I hope I can get some guidance here. The question provides us with a public key, $N$ and the padding scheme.
This is the padding scheme "Assume ...
