Newbie here. Not familiar with cryptography; just interested and reading up about it from time to time.   We know that the RSA problem (let's say $c=m^e \bmod N, c^d= m \bmod N$) is about recovering $m$ given $N, c$ and $e$. However, if given $N, m, C$ and $e$ - can I recover $d$?
26807
Assume Alice and Bob are using RSA to create a common session key and Cindy is listening, attempting to obtain the session key.  Alice and Bob each have their public- and private-key pairs ($\left[pub_{A}, pri_{A}\right]$ for Alice and $\left[pub_{B}, pri_{B}\right]$ for Bob) and Alice, Bob, and Cindy all know everyone else's public key.   Alice generates a random $n_{A}$ and sends out $En_{pub_{B}}\left(n_{A}\right)$ ($n_{A}$ encrypted with Bob's public key). Bob generates a random $n_{B}$ and sends out $En_{pub_{A}}\left(n_{B},n_{A}\right)$ and sets the session key to $n_{A}\oplus n_{B}$. Alice sends out $En_{pri_{A}}\left(n_{B}\right)$ and sets the session key to $n_{A}\oplus n_{B}$.   My thinking is, Cindy decrypts message 3 with Alice's public key to obtain $n_{B}$.  Now Cindy has a plaintext, ciphertext pair and the key that decrypts the ciphertext.  My question is, is it possible with this information for Cindy to find $pri_{A}$ in order to decrypt message 2 and find $n_{A}$?
53694
I came across this theorem:   For all integers a,b,c and m&gt;0, if d = GCD(c,m) then a*c ≡ b*c (mod m) iff a ≡ b (mod m/d).  The =&gt;proof states this:  a*c ≡ b*c (mod m) =&gt; m|(a-b)*c                    =&gt; m/d | (a-b)*c/d                   =&gt; m/d | (a-b)                   =&gt; a ≡ b (mod m/d)   I don't understand how to go from step 2 to step 3. The proof states that this is possible because m/d and c/d are coprime. To me this means GCD(m/d, c/d) = 1 but how does this cancel out the whole term?
101847
I have been reading about . I was wondering if this attack is feasible while signing with RSA and, if yes, how?    Also, how this kind of attack is applied with DH?   Talking about timing attacks in general, in which way AES is affected and how to solve it? (I mean, with RSA the "problem" is at multiplication level, while for AES where is the problem that makes the cipher implementation key or data dependent?)
22267
I am trying to make the RSA structure of Openssl manually, knowing the public key ($n$, $e$) and the  parameters $p$, $q$, $d_P$, $d_Q$, and $u = q^{-1} \mod p$.  That is, I want to get the $d$ value (private exponent) of the RSA structure by using Openssl API. If there are already any implemented functions, it would be great to me.  Bonus question: is it possible if I have $p$, $q$, $d_P$, $d_Q$ and $u$ but not the public key? I know that $n = p q$, but what about $e$?
61554
If we multiply 2 number and take the mod with prime this is equivalent to first taking mod with the prime of individual number and then multiplying the result and again taking mod.  $$ ab\bmod p = ((a\bmod p)(b\bmod p))\bmod p$$  does there exist any proof for this?  Does it work for composite moduli too? Then I can use the Chinese remainder Theorem to calculate the result does there any other way apart from Chinese remainder Theorem to solve the problem?
90692
I am trying to understand how to calculate the modular reduction of Rijndael's finite field.  The example on  page says that {53} • {CA} = {01}, because (11111101111110 mod 100011011) = {3F7E mod 11B} = {01} = 1.  I am able to get to the point where I have 3F7E mod 11B, but cant seem to figure out how the reduction works.        11111101111110 (mod) 100011011      ^100011011             1110000011110       ^100011011             110110101110        ^100011011             10101110110         ^100011011             0100011010            ^100011011 &lt;-- here, right shifted two places?             00000001   From this example, why does it right shift two places at one point?  I also found an example that 0x1b*0xaa equals 0x8c. Trying to solve this myself I get to the point: 0xE0E mod 0x11B   111000001110 ^100011011   11011010110  ^100011011    1010111010   ^100011011     010001100    ^100011011      10010111   This makes it 0x97
81102
As you know, in RSA encryption, we calculate an n value by multiplying two long primes. Then we calculate Φ(n), which is equal to (p-1)(q-1). After that, we choose an encryption key which satisfies gcd(e,Φ(n))=1. I know that it is necessary to calculate decryption key, which is the modular inverse of e. My question is: Why do we use Φ(n) in determination of encryption and decryption key processes? How can one prove it is working for RSA encryption?
58415
EDIT: Just wondering why was this question closed as a duplicate of a question asked almost 2 years after this one... I've seen an example of how to sign using RSA. Besides the signing itself (s = m^d mod n) it also hashes and adds an IV. Why is that needed?
15506
It's been over 30 years since Rivest, Shamir and Adleman first  described their algorithm for public-key cryptography; and the intelligence community is thought to have known about it for around 40 years&mdash;possibly longer.  It's fair to assume that, during those 40 years, certain three-letter organisations have employed their vast resources toward "breaking" RSA.  One brute-force approach may have been to enumerate every possible key-pair such that, upon encountering a message known to be  encrypted with a particular public-key, they need merely lookup the associated private-key in order to decrypt that message.  Signatures could be forged similarly.  How reasonable is this hypothesis?  How much computing resource would have been required over those 40 years to enumerate every possible {1024,2048,4096}-bit key-pair?  I think it best to avoid discussion and leave the question of whether the spooks could have harnessed such resource as an exercise to the reader.
11700
I know and I have understood the details of RSA, elliptic curve cryptography, (EC)DH and (EC)DSA.  I keep reading everywhere that (if we don't consider non-deterministic computers) "ECC can achieve the same level of security as RSA, but with lower key sizes". While I can guess why this is true, how do we mathematically prove that?  Here's what I think:   The fastest algorithm for the ECC discrete logarithm problem is the Baby-step Giant-step, which is $O(2^{b/2})$ (). The fastest algorithm for the RSA problem/integer factorization is $O(\exp((64 b / 9)^{1/3} \cdot (\log b)^{2/3}))$ ().   Here $b$ is the bit-length of the key/of the group order.  Therefore, an ECC key of $b_1$ bits has the same strength of an RSA key of $b_2$ bits when: $2^{b_1/2} \approx \exp((64 b_2 / 9)^{1/3} \cdot (\log b_2)^{2/3})$.  Using that formula I can calculate that if I have a 2048-bit RSA key, I can achieve the same level of security with a 273-bit ECC key. But this number (273) is too high.  My question is: is my reasoning wrong? Where is the mistake?
23844
When using the RSA cryptosystem, does it still work if you instead encrypt with the private key and decrypt with the public key? What about in the case of using RSA for sender authentication?
79550
Whilst I understand how the RSA algorithm works, I don't understand how the CPU operates when it needs to use the mod function with a huge number $n$, for example.  $n = 8192$ bits; $c = m^e \mod n$;  In essence my question is how does the CPU deal with this huge modulus?
111629
While studying the RSA algorithm I referred to some books and some sites such as  and all of them chose {d,n} as the secret (private) key and release {e,n} as the public key but as d and e are multiplicative inverse of each other, can't we keep {e,n} as private key and use the other as public key? Is it a standard rule to choose the {d,n} as the private key?
113601
I am trying to figure out how to complete RSA manually.  I am trying to encode a simple block message (Mi).  I used CrypTool to determine the encryption.  When I &quot;manually&quot; computed the plaintext, I obtained a different number than what CrypTool provided.  Can someone guide me?  Am I doing the manual encryption for RSA correct?
31547
I was given a cryptography question during an interview the other day.   Imagine you are given an efficient algorithm which for a given RSA public key (n,e) is able to decrypt 1% of the messages encrypted with that key.   1% means that the algorithm will deterministically decrypt 1% of all possible ciphertexts on the first call, and will never decrypt the other 99% of all possible ciphertexts with any number of invocations.   Figure out an algorithm that uses this one and can decrypt any message. Any ideas?
3348
I was wondering how many possible private/public keys exist? If a million people – for whatever reason – would try to generate 5 keys each in the same minute (on the same date and time) is there a high chance of collision? I believe GUID would suffer from that problem as many bits are reversed for date/time (and GUID version) and isn't meant to be used in that way.  Would RSA suffer from collisions if many keys were to be generated in the same moment? Is the amount of possible keys known? I know RSA is based on prime numbers and small numbers are to be rejected. I’m sure values above a certain amount of digits/bits are rejected because software may not be able to support those large values?  So: How many RSA keys before a collision? And if you would try to make many at the same time, would that give you a high chance of collision?
21258
Prove that the multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime.  Can someone help me with this?