Tag Info

Hot answers tagged

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

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

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

Signature verification is failed because you are using a different public key in the verification method. Use the public key to verify the signature which is consistent with the private key that is used into rsaSign() method. Hope this will help you. Note that, this public key is consistent with the private key which is used in Signature Generation method : ...


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 ...


1

Because RSA takes advantage of the fact that: $a^{\phi(n)} \equiv 1 \mod n$ Which means: $a^{\phi(n)+1} \equiv a \mod n$ So, in order to encrypt and decrypt using $e$ and $d$, we need: $ed \equiv 1 \mod \phi(n)$ Which can only be true if $gcd(e,\phi(n)) = gcd(d,\phi(n)) = 1$



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