Tag Info

Hot answers tagged

6

I don't know about computing things in parallel, so I will ignore that part of the question. First, please note that the encryption algorithm is rarely the the weak point of the security. It is far more likely that you will have problems with the implementation, some spyware installed on your computer, a weak password (If you use qwerty as your password, ...


3

512 bits (rounded down from the 664 bits or 200 digits in the patent) was recommended from its conception in 1974 and throughout the 1980s. Indeed, 463 bits was considered sufficient in the mid-1990s for the RSA-140 challenge. Whether key strengths as low as 100 digits (330 bits) were ever used in the early 1980s embedded systems is unclear; but probable ...


3

For part(a.ii), I am presuming that "enumerating candidate prime factors" means that we have a precomputed list of all 1536-bit primes, which we can simply test one at a time. To determine average running time we can use the prime number theorem, which states that the number of primes less that $N$ is approximately given by $\pi(x) \sim \frac{N}{\ln N}$. ...


3

Calculate $\phi(n) = (p-1) (q-1) = n - p - q + 1$. Then $d = e^{-1} \mod \phi(n)$. With OpenSSL, the code should look something like this (error checking omitted): BN_CTX *ctx = BN_ctx_new(); BIGNUM *d = BN_dup(n); BN_sub(d, d, p); BN_sub(d, d, q); BN_add_word(d, 1); BN_mod_inverse(d, e, n); BN_ctx_free(ctx); return d; The inverse calculation is less ...


2

They rely on problems not so different as you might think. They are based either in the factoring problem or in the discrete logarithm problem, which have a deep connection between each other. Once you have an algorithm that can efficiently solve one, you most likely would be able to adapt it to reproduce an answer for the other in polynomial time. Thus ...


2

You never need larger parameters for RSA. In the worst case ElGamal parameters and RSA parameters are equal size. But you can significantly reduce ElGamal parameters depending on the setting you are using for ElGamal. If you are working in $Z_p$ for $p$ beging prime, you work in a field of the same bitlength as required for RSA. But to obtain IND-CPA ...


2

RSA and ElGammal are about equally secure at the same modulus size (assuming, of course, intelligent parameter selection in both cases). For RSA (assuming you use good padding), the best known-attack is to factor the modulus with NFS. For ElGammal (assuming you use a subgroup with a large enough prime factor), the best known-attack is to compute the ...


2

Check out the notes of paragraph 9.2 of that document, it lists all the encodings in hexadecimal values. It does so for PKCS#1 v1.5 padding for signature generation, but it certainly contains the OID's internally - 06 LL { OID } where LL species the length of the BER encoded OID: For the six hash functions mentioned in Appendix B.1, the DER ...


2

The question is from Problem 2 in Assignment 6 given here. It looks much like a straight instance of the RSA problem: we want to find $x\in\mathbb N$ such that $x^e=E\bmod R$ and $x<R$, given $R$, $E$, $e=7$, with $E$ expected to be the product of two unknown primes $p,q$ such that $e$ is coprime with $(p-1)\cdot(q-1)$. It is correct that knowing none of ...


2

DP is $d\bmod{p-1}$, similarly DQ is $d\bmod{q-1}$. InverseQ is $q^{-1}\bmod{p}$. These are used in applying the Chinese Remainder Theorem to RSA decryption, which is an optimization technique.


1

Yes, this is doable. Here is a construction, built out of several basic primitives: Let $R$ be a randomized primality generation algorithm; there are many of them. It uses randomness, so let's make the bits of randomness it uses explicit as input: $R(c)$ is the output it produces, when given a random number generator that outputs the random bits $c$. ...


1

For $n$ and $n'$ RSA moduli of a size of practical interest (1024-bit and more) and correctly generated, we can say that the expected computing effort to factor both $n$ and $n'$ by any practical method that we know (including the best, which is GNFS) is about twice that to factor $n$. How that translates to time is context-dependent. In particular, the ...


1

I have used the following python code to compute the private key and perform decryption. It uses the extended euclidean algorithm: def egcd(a, b): x,y, u,v = 0,1, 1,0 while a != 0: q, r = b//a, b%a m, n = x-u*q, y-v*q b,a, x,y, u,v = a,r, u,v, m,n gcd = b return gcd, x, y def main(): p = ...


1

Some observations, though I would recommend against inventing your own protocol, at least for real world use: When a new Chat group is formed, a random AES Key is generated and encrypted using each users public key. This means the protocol lacks forward secrecy. Anyone who compromises the private key of a chat participant can decrypt any previous chats ...


1

In the context of RSA, when we say an "N bit prime", we mean that it's a prime in the range $[2^{n-1}, 2^n)$. In addition, when we say an RSA key is an "N bit key", we mean that it's in the range $[2^{n-1}, 2^n)$. What this means that if you pick two random $N/2$ bit primes, and multiply them together, you'll get an $N-1$ bit modulus about half the time. ...



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