# Tag Info

1

I just want to highlight: The new advancement need to be realized and validated. ECC and DH are quite similar although ECC discrete logarithm problem is harder. In other words, whatever effects the security of DH might not affect ECC with the same magnitude.

11

A couple things: This article is two years old, so take its predictions with a grain of salt. In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon. The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those ...

1

$d$ must indeed be an integer. To calculate $d$ you need to calculate $d=e^{-1}\bmod{\phi(n)}$ which is called the modular multiplicative inverse of $e\bmod{\phi(n)}$. For $d$ be computable you need to ensure that $$\gcd(e,\phi(n))=\gcd(e,(p-1)(q-1))=1$$ holds, which isn't the case with your sample parameters as $\gcd(3,60)=3\neq1$. As fgrieu pointed out ...

2

No, in the end the private exponent $d$ is just a number within $0..N$ where $N$ is the modulus. It depends on $N$ what the chance is that the first bit is one, but in more likely to be valued $0$ than $1$ (given that it is well distributed, you would expect it to be $0$ around $\frac23$ of the time). If you generate enough private keys you'll even see ...

2

In general there is no default hash algorithm in the PKCS#1 standards, neither for RSA with PKCS#1 v1.5 padding or RSA with PSS. Both these schemes are defined in RFC 3447 RSA PKCS#1 v2.1. Note that PKCS#1 v2.2 adds a few SHA-2 hash functions (SHA-224 and SHA-512/224 and SHA-512/256) to the mix - neither of which makes much sense. PSS uses a Mask Generation ...

0

It seems you are well on your way to understanding the attack. After you compute the GCD of these two polynomials you are left with a polynomial of the form $X - m$. It is clear why—if $f_1(X) = X^3 - C_1$ and $f_2(X) = (X + p)^3 - C_2$ have a common root $m$, then they are of the form $(X - m)g_1$ and $(X - m)g_2$, for some arbitrary $g_1$ and $g_2$. So, ...

0

I found my answer from a different question very similar to mine from this(crypto.stackexchange). Hope it helps.

1

If you are able to compute $m^1 \pmod{N}$, then you have (obviously) recovered the message $m$. So, you should be able to use the extended Euclidean algorithm to express $m^1 \pmod{N}$ in terms of $c_A$ and $c_B$. Hint: It will involve exponentiations and multiplications.

1

See step 3, 4 & 5 of 9.2 EMSA-PKCS1-v1_5 that defines the PKCS#1 v1.5 padding mechanism for signature generation: If emLen < tLen + 11, output "intended encoded message length too short" and stop. Generate an octet string PS consisting of emLen - tLen - 3 octets with hexadecimal value 0xff. The length of PS will be at least 8 ...

28

The answer is in the source, file sshrsag.c, line 9: #define RSA_EXPONENT 37 /* we like this prime */ This value $e=37$ matches the conditions for a reasonable fixed RSA public exponent: $e$ is odd, $e$ is at least $3$, $e$ is reasonably small. The later condition is good for speed of operations involving the public key (encryption, ...

11

Any $e$ such that $\gcd(e, (p-1)(q-1)) = 1$ will do. There is no need for it to be in the set $\{3,17,65537\}$; these last numbers are chosen for speed of encryption, mostly (two set bits leads to faster computation of modular exponentation), and these numbers happen to be prime, so the condiiton is easily checked. One often encounters other $e$, but many ...

2

Yes, asymmetric encryption is slow compared to symmetric encryption. With symmetric ciphers, encryption and decryption speed can be several gigabytes per seconds on a common PC core; see these benchmarks. With RSA encryption, on comparable hardware, we are talking tens of thousands encryptions per second, and only few hundreds of decryption per seconds, ...

4

What i don't understand is how it gets easier to reverse this function when you know the primes that you used to calculate the divisor Well, we know how to compute square roots modulo a prime; that is, how to solve the problem $a \equiv x^2 \pmod p$, for prime $p$ (assuming, of course, if there is a solution; there might not be one). In addition, if we ...

-1

well I sort of came up with this method , I dont know whether most people already know this or not. For every example in my text book this method has worked d= [ɸ(n) * (y)]+1 divided by e. here y = 1 , 2 ... eg p=5 , q=11 e=3 n will be 56 and ɸ(n) = 40 d= (40 * 1) +1 / 3 = 41/3 = 13.66 --- but this is not an whole number so d= (40 ...

0

This is basically a substitution cipher where words are converted to numbers and then those numbers are substituted for new numbers as the encryption step. You'd need to assume the language of plaintext, let's assume it's English. Every time the word "the" occurs in the original text, it will cause the same number to be output to replace it. Using some ...

3

Your problem is not with the signature scheme, something else is wrong. RSA is specified by the RSA cryptography standard, PKCS#1 (mirrored in various RFC's). The PKCS#1 v1.5 padding was introduced in version 1.5 but it persisted in 2.0, 2.1 and 2.2. Those did however introduce a more secure padding scheme called PSS. Unfortunately nobody calls the ...

0

Since you are approaching this from the point of view of mathematics, I think the most fruitful avenue would be to look at asymptotic performance and security of the problems that the cryptosystems are based on. For example, with RSA you need a modular exponentiation for every message you encrypt or sign. The time that takes depends on the length of the ...

1

Running RSA backwards would imply cracking the key (determining the private key) and you could brute force that by factoring. You could generate all possible prime's of the requisite size until you could generate the known public key. Or perhaps there are other approaches that are more mathematical, that could factor for the primes, which would also be a ...

0

The concept of using an asymmetric key (RSA) to encrypt a symmetric key (AES) is not new. This was first popularized by PGP, which is probably what I would encourage you to use to solve your problem. SSH (well SFTP in particular) also uses a somewhat similar approach and could also be pressed into transmitting files securely. Pretty much any approach you ...

1

See https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29 Under Key Generation: Compute n = pq. n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.

1

This sounds like Kerberos. ( https://en.wikipedia.org/wiki/Kerberos_%28protocol%29 ) In any case, you didn't mention, but it would seem quite important, how long are the generated auth tokens valid for, or how would you expire one. There is no such thing (IMHO) as permanent/indefinite authorization--if you believe otherwise, you should not be doing ...

3

In asymmetric crypto including RSA, we ALWAYS encrypt with the public key, and decrypt with the private key (NEVER the other way around). In the question, what's wanted is to sign with the private key, not encrypt. And that's enough to solve the whole problem, since RSA signature schemes exposed in BouncyCastle or the Java crypto API allow to sign data of ...

0

I have seen this before in Java. Java's BigInteger class requires and generates binary data as signed little-endian. If the high bit of the first byte is set, the whole number is interpreted as negative. In order to represent a 1024-bit number in which bit 1023 is set, it's therefore needed to add a 00 byte to the beginning, because otherwise, it'd be ...

8

You are looking at the ASN.1 encoding of private (and public) keys; the 00 values you see are an artifact of how ASN.1 encodes integers. ASN.1 is a method for describing data structures, and has ways to represents all sorts of data types. It wasn't designed with public keys (or cryptography) in mind; it was intended for more general use, initially ...

0

If you want to try with some Python code: def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m

1

Yes it proves that $y \ne 1 \pmod{n}$ is not an $e$-th root. That is, no $x$ exists such that $x^e = y \pmod{n}$. In particular, if $e | \phi(n)$ then for any $x$ it holds that $\left( x^{ \frac{\phi(n)} {e}} \right)^e = 1 \ne y$. This probably means one last final conclusion designed as a homework. Regarding GQ protocol: prover will be unable to pick an ...

0

Seeing code might help you, it should be this if I remember correctly. For large numbers you should use an NTL library. /* Recursive version of the euclidean algorithm, because it's much faster. */ void extendedEuclid(long a, long b, long& x, long& y) { if (a%b== 0) { x = 0; y = 1; return; ...

0

Wolfram alpha can do this: http://www.wolframalpha.com/input/?i=multiplicative+inverse+of+65537+mod+265291078722948385056973898354378582740 yields d = 240894030773496778838526583320400223673 The alternative is to write a small C program using gmp or using python, e.g.

3

The requirement was introduced in IUT Recommendation X.509 (November 1993), informative appendix D.5.2: It must be ensured that e > log2(n). If not, then the simple operation of taking the integer eth root of a ciphertext block will disclose the plaintext. This advice was removed in the 2000 edition of the standard. It is arguably misguided, and at the ...

4

Assuming you manage to safely generate RSA keys which are sufficiently large, i.e. >= 2048 bits, no TLS configuration flaw on your side, and the lack of security bugs in the TLS library used by your server or the one used by the client user agent, I do not believe TLS_ECDH_RSA_WITH_AES_128_GCM can, at this point, be decrypted by surveillance agencies. ...

5

RSA is and was specified by the PKCS#1 specifications of RSA laboratories. PKCS are the "Public Key Cryptography Standards" by RSA Laboratories, now part of EMC2. The RSA PKCS#1 v1.5 is the lowest publicly released version of RSA by RSA labs that can currently be downloaded. Version 1.0 to 1.4 are working drafts as specified in the PKCS#1 documents ...

3

You don't seem to understand what complexity means. $O(Cn^2) = O(n^2)$, so “finding $C$” is not a valid question – any positive $C$ will do. I recommend looking up some basic complexity theory introduction. There are many introductory books on the subject which can help you understand what this means.

5

Adding some more information to fkraiem's answer: The encryption in the Rabin cryptsystem is basically textbook RSA with an exponent of $2$. 1) Neither p nor q are equal to 2. This means they are odd. The product of (p−1)(q−1) would be even i.e. not coprime with 2. Well, yes. That is one of the basic problems in Rabin's cryptosystem. If we want that ...

3

I see you use the same generator on both sides (this need not work for any $n_1, n_2$ of course...). But even if this holds (trying a small example): Let 1 use $n_1 = 11, M=2$, and 2 uses $n_2 = 13, M= 2$. Check that $2$ is a generator for both of the multiplicative groups. If $d_1 = 7, d_2 = 9$, then $A = 2^7 \bmod 11 = 7$, while $B = 2^9 \bmod 13 = 5$. ...

8

Yes you can use Big-O notation to express runtime, that's customary. Formally, that does not give an upper bound on runtime for any fixed parameters, much less a lower bound; formally, that gives you an indication of how an upper bound would behave when some parameter grows to infinity, and no practical indication. However, in practice, when dealing with ...

1

MIGJAoGBAKv4...................3VpXAgMBAAE= 30818902818100 ABF8... ...DD5A57 0203010001 7 5 Overhead & public exponent are 7 + 5 = 12 bytes. You have a 1024 bit modulus = 128 bytes. So a correct encoding would be 12 + 128 = 140 bytes, requiring ceil(140 / 3) = 47 * 4 = 188 base 64 characters. You however ...

2

Note: In my answer below I neglected to consider that the the messages for the associated signatures are also known, and that this could enable the existence of a practical algorithm to recover the modulus. While I haven't done the legwork to verify, fgrieu's comment below indicates that recovery of the modulus may very well be practical. I'm leaving my ...

2

Yes, it is possible to change the public encryption exponent of an RSA key. Indeed, this requires no special computation. An RSA public key consists of two numbers: the modulus $n$, which is a product of two large (secret) primes $p$ and $q$, and the encryption exponent $e$, which is usually a small fixed prime (most often, 3 or 65,537 = 216+1). If you ...

0

Now that of course gets more complicated with bigger numbers too, but still quite easy/fast. So basically if those numbers are not primes, that you can just split up $n$ as much as possible and from there you have an easier way to find $p$ and $q$. If both are primes you have to try values for $p$ and $q$ until you find exactly the right values.

3

calculate $$gcd(c_1^e - m_1 , c_2^e- m_2, \dots , c_k^e-m_k)$$ With a bit luck this should get $n$. It will be an interesting exercise to calculate the probability of success based on the number of cleartect/ciphertext pairs.

0

As @Myria describes one common RSA signature scheme, defined in the original PKCS#1 as type 1 and retronymed RSASSA-PKCS1-v1_5 in the nearly current version encodes the hash inside the value computed modexp d (and modexp e for recover/verify). Other important RSA schemes like PSS and 9796 do not, and other algorithms like DSA and ECDSA cannot, so systems ...

0

For the problem of determining the base ($m$), the problem is that you don't have enough information. For any valid value of $e$, there is a matching value $m$ that encrypts to the same $c$; specifically, $m = c^d \mod n$. Because there are many, many possible answers, there's no way to determine this, unless the value of $e$ is very small or predictable, ...

0

Assume the public key $e$ is not known, how difficult would it be to guess the public key using $n$, $\phi$, $p$ and $q$? $e$ can be chosen completely arbitrary and independently of the modulus and related variables ($\phi,p,q$). You can't learn anything about $e$ (assuming $d$ isn't given) only with the modulus given. Assuming we have $c_1$, $c_1 ... 1 RSA with$e = 2$is Rabin, it works a bit differently and is slightly more mathematically involved, but it is a valid cryptosystem. 1 For the purposes of your high school project, I suppose either one is fine. As you mentioned, one possibility is to convert the message to a bit-string using ASCII, and then interpret the bitstring as an integer and treat it as the message to be encrypted. If you need to "show your work" on paper or slides, then writing it in decimal is reasonable. However, ... 0 I think I found the answer to my own question... First 'Hello' is represented in binary form (ASCII) - after that, the integer in binary form is converted to decimal form. 4 The method mentioned in the answer by Maarten will allow you to reduce the private key size for any public key algorithm by regenerating the key from a random seed, each time you need it. The drawback is the performance. Each time you need to use the key you need to spend as much CPU time for regenerating the key as you used for generating it the first ... 5 My question is: what does 'large' imply? How many digits - is there a 'limit' to the amount of digits for an suitable prime? A prime$p$is called large in this case if factoring the multiplication$pq$with a similar-sized prime$q$prime is considered infeasible. Usual sizes of the primes include$2^{1024}$up until$2^{2048}\$. For the recommended ...

Top 50 recent answers are included