# Tag Info

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

0

A. J. Menezes et al., Handbook of Applied Cryptography (available online) 4.62 gives Maurer's algorithm for generating provable primes, which is fairly competitive in runtime with probabilistic methods (commonly employing Rabin-Miller test) for sizes of primes of practical interest. I have recently implemented Maurer's algorithm in Python ...

0

What you are proposing is bad. RSA-KEM uses RSA encryption without padding, but not in the way you are proposing. See the second part of its Wikipedia Page The problem with your construction is that if you encrypt a short message (i.e. AES key) with RSA without padding, then it might get decrypted through e-rooth calculation or through Coppersmith. It ...

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

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

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

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.

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

0

Basically you are talking about “superencipherment”. This has a long history in cyptography, but it eats up space like crazy. Your observation of PK cyptography being vulnerable is true. Solving 'Prime' would bring the house down.

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

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

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

Top 50 recent answers are included