1
$\begingroup$

Math algorithms like Karatsuba and derivatives - do they have any applications for cryptanalysis of asymmetric cryptography algorithms? What if we have very fast multiplier? How can it help with extracting the secret key from encoded text?

$\endgroup$
  • 7
    $\begingroup$ When you say "How can it help?" do you mean in supporting cryptanalysis or in thwarting cryptanalysis? If you mean thwarting, perhaps it could eliminate side-channels. For supporting, perhaps it could make your attacks faster. I think your question could be helped significantly by narrowing the scope and giving some examples. $\endgroup$ – mikeazo Jun 6 '17 at 14:37
3
$\begingroup$

Since Karatsbua is often the default multiplication method for any library with big integers, this is surely used in cryptographic algorithms - whenever large integers are involved. Typical examples for this are RSA, DH key exchange, DSA, all elliptic curve cryptography, etc.

The runtime of Karatsuba depends only on the lengths of the numbers and not on the actual number itself, reducing $n^2$ single-digit multiplications (for long multiplication) to $\approx n^{\log_2 3}$ (exact number depends on the input lengths) and some additions (also only depending on the length of the numbers). So if we can assume constant runtimes for the addition and single-digit multiplication, this should not leak any information. It is just faster.

do they have any applications for cryptanalysis of asymmetric cryptography algorithms?

I am not sure what you actually mean. Sure, they do have applications: Whenever there is a multiplication of big integers, Karatsuba is used already. But Karatsuba does not give you any other surprising advantage, as far as I know.

What if we have very fast multiplier?

I don't know why the question i stated in such a hypothetical way, because that is actually how multiplication is realized. For integers, long multiplication is actually the rare case - that's how it is taught in school and mostly used for multiplication by hand.

How can it help with extracting the secret key from encoded text?

It can't. Actually, I am not sure what you mean with this question. For any state-of-theart encryption scheme with proper parameters, it is practically impossible to extract the key from a ciphertext - if we assume lmitations in time and computation power like "If every atom on earth was a computer and we could use a Dyson sphere around our sun to produce energy until the sun burns out". It is a common misconception, that encryption can actually be broken in such a way.

But coming back to fast multiplication algorithms: In some cases, other methods like Discrete Fourier transform-based multiplication is used, e.g. this can be used to speed up the Miller-Rabin primality test.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.