# Tag Info

0

You haven't done enough research. There's a ton of information on attacks on the discrete log problem modulo a prime (which is what is relevant to your situation), including some concrete examples of sizes of primes for which discrete logs have been successfully calculated and key size recommendations. In particular, 120-250 bits is nowhere near enough for ...

1

Considering the padding as an addition, padded message passed to sign is $m\cdot 2^{16}+0101$, $0101$ in hexadecimal, assuming padding is done on the lower bytes (for higher bytes the logic is just the same). Being $e$ the private exponent, and $m^2$ computed in the size of $m$, $(m\cdot 2^{16}+0101)^e \pmod m$ is very different from $(m^2\cdot ... 3 The probability of such a "collision" occurring randomly, with honestly-generated RSA keys, is extremely low. Mathematically justifying that assertion can be tiresome, but the idea is the following: Let$s$be a RSA signature, i.e. an integer of size$k$bits for some$k$(e.g.$k = 2048$). We consider RSA keys$(n,e)$where$n$is the modulus (of size$k$... 1 Accordingly to a previous thread Why is elliptic curve cryptography not widely used, compared to RSA?, RSA is still widely used compared to ECC because: RSA is well established Its public key operations (e.g. signature verification, as opposed to signature generation) are faster than ECC (most importantly) The RSA patents have expired, while a small ... 1 Being new to cryptography is one thing, but you are supposed to do some research on your own before asking questions here (see How to Ask), and D.W. gave you the right directions already. But since you wanted names and links: The first stop should be discrete logarithm on Wikipedia, and it lists several algorithms on this topic. As a beginner, start with ... 6 The first observation in the question boils down to: in textbook RSA, the encryption of$N-M$instead of$M$yields$N-C$instead of$C$. This is a special case of a more general property of textbook RSA, that the encryption of$M\cdot M'\bmod N$yield$C\cdot C'\bmod N$, whenever enciphering$M$yields$C$and enciphering$M'$yields$C'$; combined with ... 0 Yes. Use any algorithm for solving the discrete log problem. This is well-studied; do a search on "discrete log" problem and you will find lots of information, both on this site and on Wikipedia (eg this list). 0 One potential risk is your AES key length. Using a key length of 64 bits or less is not advisable as it can be relatively easy to brute force these days. Recommend that you use at least 128 bits. As for your problem when a user is removed, you may like to try something similar to PGP. Each time you commit a file to the server, you encrypt it with a ... 3 Your parameters are incorrect. I don't know how you got them, so I don't know which one is in error; however at least one of them is wrong. You have$n = 149 \times 191$. The decryption exponent satisfies: $$ed \equiv 1 \pmod{\operatorname{lcm}(p-1, q-1)},$$that is,$7d \equiv 1 \pmod{14060}$; the minimal$d$that satisfies this is$d = 10043$. Now, if ... 0 RSA encryption and decryption is built upon Fermat's theorem which says:$a^{\phi(n)} = 1 \mod(n)$, and since$p$and$q$are primes:$\phi(p*q) = (p-1)*(q-1)$. If we have message$M$and private key$d$and public pair$e$… Encryption:$C = M^e (\mod n)$Decryption:$C^d \mod(n)$which most be the same as$M$Now,$C^d = (M^e)^d = M^{(ed)} \mod(n)$. ... 0 I think that number OTP 4x4 XXX-XXXX-XXXX-XXXX is in Base64 Alphabet, so convert this to Decimal and you have a big Integer. Factorize, and you'll obtain a couple of primes numbers, with which you can to generate a public and private key. With those keys, using the Euler law (RSA Encryption base) you can decipher the password. 8 It doesn't become vulnerable; instead, it becomes impossible to decrypt uniquely. Let us take the example you give:$N=65$and$e=3$. Then, if we encrypt the plaintext$2$, we get$2^3 \bmod 65 = 8$. However, if we encrypt the plaintext$57$, we get$57^3 \bmod 65 = 8$Hence, if we get the ciphertext$8$, we have no way of determining whether that ... 1 Yes, it does make sense to block them. Seeing you've asked this question in July, it's funny to think you might have had some kind of unintentional foresight of what meanwhile has become reality. Some hard facts: As raw computing power increases over time it becomes possible to factor or crack smaller sized RSA keys. Key sizes smaller than 1024 bits were ... 1 Many of the beginner explanations use very simple examples: like this It is still hard to factorize a small number by hand, compared to other operations. There is definitely a size of prime numbers where hand computation is still feasible, but hand factorizing isn't. Would you, for instance, even armed with a list of primes, be able to quickly tell me what ... 3 I just want to add some additional information to the answer of Ilmari. As Ilmari has already described in his answer, when using RSA you work in the ring of integers${\mathbb Z}/{\mathbb Z}_n$, which is also called a residue class ring. This means that it consists of the set of residue classes$[i]$, where the$i$'th class is defined as the set$\{a ...

6

As mikeazo notes in the comments, RSA operates on the ring $\mathbb Z / n\mathbb Z$ of integers modulo $n$, for a given modulus $n = pq$. In this ring, $$E(m) \cdot t^e \equiv m^e \cdot t^e \equiv (mt)^e \equiv E(mt)\ \pmod n.$$ In particular, for $n = 35$, $e = 23$, $$17^{23} \cdot 2^{23} \equiv 33 \cdot 18 \equiv 594 \equiv 34 \equiv 34^{23}\ ... 0 A Semiprime is the product of two prime numbers. Such numbers, i.e. semi primes, if enough large, as used in RSA, are very difficult to factorize. Since there is not enough computational power or a mathematical solution to factorize large prime numbers, the strength of the RSA stands. Currently, 2048-bit numbers are used in RSA for generating these keys, and ... 0 I figured out the decent way of solving for d (the private key). I have n=35, with (p,q)=(5,7). I have also computed \phi(n)=24, and selected e such that \gcd(e,\phi(n))=1 by taking e=23. To calculate the private key, we need to use the formula:$$d = e^{-1} \mod \phi(n) This gives us $d = 23$, which happens to be the same as $e$, a ...

3

The main misconception here is, what part of the RSA problem is actually hard to compute. Your statement is like this: We have $e$ and $n$. We know $ed=1$ mod $\phi(n)$. So we should be able to calculate $d$. Your reasoning is exactly what is happening in the key generation algorithm. Division in modular arithmetic behaves just the same as with ...

1

The private key $d$ of RSA algorithm with public parameters $(N,e)$ is such that: $ed \equiv 1\mod{\phi(N)}$. Since by definition $e$ and $\phi(N)$ are coprime then with extended euclidean algorithm you can find such $d$: $ed +k\phi(N)=1$ Consider that to compute $\phi(N)$ you should know how to factor $N$ since $\phi(N)=\phi(p)\phi(q)=(p-1)(q-1)$ To see ...

3

Are you asking "given $e$ and $\phi(n)$, how do we find $d$ such that $de \equiv 1 \bmod \phi(n)$"? (which can also be written as $d = e^{-1} \bmod \phi(n)$ The standard way of find such a value is the Extended Euclidean Method; this is a relatively efficient method that results in $d$ given $e$ and $\phi(n)$ as inputs (assuming, of course, that $e$ and ...

5

You are correct in that knowing $\phi(n)$ it is trivial to get the private key back with a simple modular inversion. However, we are only given $e$ and $n$, and it turns out that computing $\phi(n)$ from $n$ alone is computationally equivalent to finding the factors of $n$. Namely, if you know $\phi(n) = (p-1)(q-1) = (p-1)(n/p - 1)$, you can recover $p$ by ...

1

If you use the raw RSA operation ($M^d \bmod n$ or $M^e \bmod n$), then no, it is unsafe to use the same key, because an attacker could trick the private key holder into signing a message $M$ (i.e. generating $M^d$) which is actually an encrypted message ($M = P^e$), thus allowing the attacker to recover the original plaintext ($(P^e)^d = P$). (The dual ...

3

Short Answer: NO, it is not safe, do NOT do this. Longer Answer: You are true that you can use your RSA keypair for both operations. This approach is used in many applications and scenarios. There are Web Services or Single Sign-On implementations, which enforce you to use the same key pair for both operations. X.509 certificates do not allow you (by ...

2

We don't say this can't happen, we just say it won't happen. The only value that will decrypt to $p_2$ under $(e_2,n_2)$ is $p_2^{d_2}$, which we can call $s_2$. So, your problem comes down to asking what is the probability that $s_1=s_2$? If we assume that they're random, and that the moduli are similar enough sizes that this is even a realistic ...

2

I can't remember anyone claiming that: $s_1^{e2} \bmod n_2 = p_2$ is never true. However, there is a single value $s_2 = p_2^{d_2} \bmod n_2$; it would be a rather strange coincidence if that value just happens to be the value $s_1 = p_1^{d_1} \bmod n_1$

3

The performance bottleneck with RSA is the modular exponentiation operation. On the other hand, if you are interested in public key encryption performance, perhaps RSA is not the correct tool. RSA is actually fairly fast during its encryption operation; however it is quite slow during the decryption. If you care about decryption performance, you may want ...

4

In RSA encryption as practiced (that is, to encipher a message which is a short symmetric key), the message size after padding is fixed and equal to the modulus size. Thus the size of the message has no impact on performance. Calculating a modular inverse is performed only during key generation, that is seldom. Also, it has low cost compared to generating ...

2

The first byte is 0x00, because some standards allow RSA key sizes $8b+1, b \in \Bbb Z_+$. Such key would have 0x01 at the first bit, but it is possible for almost all other bits to be zero. Thus, 0x00 as the first byte allows interoperability with all possible RSA key sizes. NIST's recommendations and few other standards actually recommend only few ...

1

No, exposing such a hash does not compromise the RSA private key, unless the hash function is sufficiently and severely broken. Of course, you don't need to hash the private exponent to identify the key. You can simply use the modulus or a hash over the (public) modulus to identify the key. This has the additional advantage that that ID will also match the ...

3

This does not compromise the private key as long as the hash function is preimage resistant, i.e. given $H(M)$ it is hard to find $M$ (or any $M'$ giving the same $H(M)$). SHA-3 is assumed to be preimage resistant.

5

No, it not possible to attack RSA (and practical modulus size) with a WalkSat derivative, as far as we know, or using the algorithm in the question. Problem with that algorithm is: in order to have a sizable/constant rate of success as $n$ increases, we have to repeat steps 2 and 3 not the stated $t\cdot m^2$ times, but rather $t\cdot 2^m$ times. That's ...

-3

RSA is secure currently as we do not have an efficient way to factorize the two primes ( within our lives anyways.. ) HOWEVER, if factoring becomes easier or when quantum computers become more large scale and accessible you can expect them to be factored within minutes.

5

Yes, RSA is secure as we know it — although recommended key sizes are ever-increasing, as expected. Any seemingly-simple result that suggests a long-studied, well battle-hardened cryptosystem is insecure should throw up red flags. As an exercise, I wrote up your algorithm in simple C code: #include <stdio.h> #include <stdlib.h> int ...

3

The issue is that we use modular arithmetic. In modular arithmetic, you may view $m \bmod n$ as the remainder of $m$ when divided by $n$. So, for example, $7 \bmod 2 = 1$, also written as $7 \equiv 1 \pmod 2$, because $2(3) + 1 = 7$. Now consider what you're guaranteed by $m \equiv c^d \pmod n$, the decryption formula for plain RSA. You're guaranteed that ...

2

The current best way of decryption an RSA ciphertext (assuming good padding was used) is to factor $N$ into its prime factors $p$ and $q$, and from that, reconstruct the decryption exponent $d = e^{-1} \bmod lcm( p-1, q-1 )$ The current record for factoring an RSA-type modulus (with large prime factors, and not of a special form) is 768 bits. It is likely ...

Top 50 recent answers are included