Tag Info

Hot answers tagged

8

The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). We can ...


5

It is highly misleading to call how RSA Encryption is used as 'ECB mode'. With ECB mode, we break the plaintext into N bit segments, and send each one through the block cipher separately. The block cipher is deterministic, and so if two plaintext blocks happen to be the same, so will the corresponding ciphertext blocks. Now, with RSA encryption, we take ...


4

You are essentially asserting that if $k \equiv 1 \pmod N$, then $a^k \equiv a \pmod N$. This is false in general. The correct assertion is the following: $a^k \equiv a^\ell \pmod N$ if $k\equiv \ell \pmod{\phi(N)}$. In more general group-theoretic terms, if $a$ is an element of order $n$ in a group $G$, then $a^k = a^\ell$ if and only if $k \equiv \ell ...


4

If $p$ is prime, then $\phi(p) = p-1$; so the question is "given $k(p-1)$, can someone get a good guess of what $p$ might be?" It is unlikely that the attacker would be able to limit it to one particular value of $p$ (as there are likely to be multiple values of $p$ that are plausible), however the attacker might be able to construct a short list of ...


3

If you can efficiently find a $P$ that is not coprime to $N$, then you can easily factor $N$ (use GCD). If you know the factorization of $N$ (say $N=pq$), you can easily find a $P$ that is not coprime to $N$ ($kp$ for some constant $k$). This established the fact that finding $P$ not coprime to $N$ and factoring are equivalent problems. Now, how many ...


2

If you know a multiple of $p$ and $k$ is smaller than $\sqrt(p)$ than you can use a different approach than the one by poncho. Note: knowing a multiple of $p$ is the typical case of RSA where you know the modulus $N$ made by $p\times q$, so if your question refers to RSA you are left only with the constrain on the size of $k$. The method you can use is an ...


2

RFC 2313 specifies the RSAPrivateKey ASN1 structure as a SEQUENCE containing the INTEGERs $0$; $n$; $e$; $d$; $p$; $q$; $d\bmod(p-1)$; $d\bmod(q-1)$; $q^{-1}\bmod p$. The PEM format consists of such a structure encoded as Base64 and framed by the typical BEGIN/END RSA PRIVATE KEY header and footer lines. Thus, you can use any ASN1 library you like to ...


2

Your calculation is broken. First as pointed out correctly the expected run-time of GNFS (general number field sieve) is: $O(exp((\sqrt[3]{\frac{64}9}+o(1))*\sqrt[3]{ln(n)}*\sqrt[3]{ln(ln(n))}^2))$. So next you can't just set these $O$s equal, as $O(f(x))$ means $O(f(x))< k*f(x)$ which means this is an asymptotic upper bound meaning you need some ...


2

The first (and hardest) step is to factor $n$; the easiest way to do this (given $e$ and $d$) is with this randomized procedure: Select a random value $z$ from the range $(2, n-2)$ Compute the value $\lambda = (ed-1)/2^k$, where $k$ is that integer that makes $\lambda$ an odd integer. Compute $t = z^\lambda \bmod n$. If $t = 1$ or $t = n-1$, we fail on ...


2

Usually the public exponent is first chosen. Often it is the 4th prime of Fermat (e.g. -f4 for openssl), 65537. This number in binary is: 0000 0000 0000 0000 0001 0000 0000 0000 0001 Fermat primes are primes with just 2 bits set. 3, 5, 17, 257 and 65537 are the only known Fermat primes. It is relatively easy to use this as exponent as only two bits are ...


1

The fastest way to solve your problem instance is as outlined in the above comments. First choose yourself a random message $m$ with $1<m<n-1$. Now compute $c\equiv m^d \pmod n$. Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$ $m \equiv c^{17} \pmod n$ $m \equiv ...


1

I don't think this problem is solvable as specified. With a small message space, and deterministic hashing (or encryption), a generic attack involves exhaustively searching all likely messages to find one that corresponds to the known hash / ciphertext. If all of the digits of the ID numbers were random, an exhaustive search would require about $10^{10} ...


1

The client generates a random symmetric key and encrypts it with the public key. This public key needs to be trusted. Make sure you use a good padding mode, OAEP should do it. Send to server, server decrypts it with the private key. Eh, that's it. No forward security though, the session can be decrypted if the RSA scheme is broken or if the private key is ...


1

You cannot, you can however create a hash over the modulus. This is sometimes used as identifier for a key pair, e.g. in PKCS#11. The modulus is unique for RSA key pairs.


1

You can't. Recovering the md5sum of the private key means uncovering the private key, which is considered impossible for large values of $n$.


1

If I'm understanding your question right, you want to obtain $d$ from given $n$ and $e$. You'll have to factor $n=33=3*11$ and as $N=p*q$ you have obtained your $p=11$ and $q=3$. Now proceed as usual with calculating the inverse. As pointed out correctly above, you can't easily generalize this approach to larger numbers as factoring $n$ will be infeasible. ...


1

The standard algorithm used for RSA encryption and decryption is exponentiation by squaring. The basic idea is to write the exponent out in binary. For example, for $d = 4267793$, $$\begin{aligned} 4267793 &= 10000010001111100010001_2 \\ &= 2^{22} + 2^{16} + 2^{12} + 2^{11} + 2^{10} + 2^9 + 2^8 + 2^4 + 2^0.\end{aligned}$$ Now, given some RSA ...



Only top voted, non community-wiki answers of a minimum length are eligible