Tagged Questions
5
votes
0answers
144 views
Prove that textbook RSA is susceptible to a chosen ciphertext attack
Given a ciphertext $y$, describe how to choose a ciphertext $\hat{y} \neq y$, such that knowledge of the plaintext $\hat{x}=d_K(\hat{y})$ allows $x=d_k(y)$ to be computed.
So I use the fact that the ...
1
vote
1answer
51 views
Comprehension question on a signature protocol based on the RSA assumption
We have the following two-party protocol between Alice and Bob. Alice sends messages $m_1, m_2, \ldots \in_R \mathbb{Z}_n^*$ to Bob and Bob signs these values by calculating $v_1, v_2, \ldots \in_R ...
0
votes
0answers
37 views
Is it possible to determine the group order by knowing the “public” and “private” key exponents in an RSA group?
I have an RSA group with modulus $n = p \cdot q$, two safe primes $p=2p'+1$ and $q=2q'+1$ and the "public" and "private" key exponents $d$ and $e$. $\phi(n) = 4p'q'$ is the order of the RSA group. If ...
3
votes
1answer
122 views
How to find an element of high-order in an RSA group?
Is this even possible? The RSA group is not cyclic, so usually you wouldn't find a generator for accessing all group elements.
What happens if you use the RSA group in a scenario where you want that ...
3
votes
1answer
72 views
Why work in a subgroup QR(n) of an RSA group $Z^*_n$?
I sometimes read in papers that a (sub-)group generator $g$ is taken from $\mathrm{QR}(n)$ instead of $\mathbb{Z}^*_n$, where $n = p \cdot q$ and $p$ and $q$ are prime. Is there a reason for this? ...
1
vote
1answer
125 views
Is this attack for RSA possible?
$N=p·q$ ($p$ and $q$ are prime numbers), $m_1, ..., m_x$ are the messages, $e$ and $d$ are RSA encryption and decryption exponents, respectively.
I am given $e, m_1, m_1^e, m_1^d, ..., m_x, m_x^e, ...
1
vote
1answer
497 views
ABC Conjecture's Impact on RSA Encryption
A recent proof of the ABC Conjecture has been released by one Shinichi Mochizuki. Now, I'm not well versed in mathematics but it would appear that this proof implies that finding prime factors could ...
4
votes
2answers
407 views
How do I solve this RSA instance for m?
How we can solve this equation and get the value of M?
$$8 = M^{13} \mod 33$$
not a computer program, but a mathematical operation.
8
votes
3answers
372 views
Is it reasonable to assure that p-1 and q-1 aren't smooth?
I came across the requirement that, in RSA, $p-1$ and $q-1$ shouldn't be smooth, shouldn't consist of lots of small factors. Therefore my question:
How complicated is it to check whether $p-1$ is ...
6
votes
3answers
439 views
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective.
RSA labs makes a similar statement:
The discrete logarithm problem bears the same ...
9
votes
3answers
2k views
What is the relation between RSA & Fermat's little theorem?
I came across this while refreshing my cryptography brain cells.
From the RSA algorithm I understand that it somehow depends on the fact that, given a large number (A) it is computationally ...
21
votes
4answers
6k views
How can I generate large prime numbers for RSA?
What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption?
I'm aware that I can find any number of articles on the Internet that explain how ...
