Re: asymmetric vs symmetric ciphers - block size?

From: Adam O'Brien (adamobrien54321_at_yahoo.co.uk)
Date: 05/19/03 

Date: 19 May 2003 14:25:13 -0700

>
> I'd hardly call an attack that uses less than the entire search space
> "brute force". In fact you can trivially break an RSA key in n^(1/4)
> time using a few line algorithm.
>
> a = b = 1
> for (;;) {
> a = (a^2 + 1) mod n
> b = (b^2 + 1)^2 + 1 mod n
> if gcd(b-a, n) != 0,1 then it divides n
> }
>
> That's the pollard-rho algorithm in pseudo-C source. It won't always
> succeed but when it does it requires O(p^1/2) time to find a factor p of
> n. In this case p ~ n^1/2 which means it requires n^(1/4) time. Of
> course when n = 2^1024 [e.g. a 1024-bit rsa key] this takes 2^256 time
> which is a tad on the long side.
>
> My point being is that brute force attacks aren't used against
> algorithms like DH and RSA [or ECC for that matter].
>
> Tom

I was careful to always use quote marks around 'brute force'. I agree
that it's odd to characterise sophisticated algorithms like GNFS as
'brute force' but I think the term is useful.
For symmetric ciphers a necessary condition for a cryptanalysis being
worthwhile is that it requires less time/space/text than 'brute
force'.
There is a parallel position for asymmetric ciphers. An attack which
'breaks' RSA quicker than factoring is cryptanalysis. An attack which
improves on factoring algorithms is maths.

Adam

Relevant Pages

  • Re: Question about bit strength
    ... around with a hybrid block cypher. ... but I am still unsure as to the bit strength of these algorithms. ... Going in approximately the order I do in performing a basic attack: ... In a stream cipher ...
    (sci.crypt)
  • Re: Side Channel Attacks - inside out
    ... > channels attack on cipher algorithms ?? ... A side-channel attack targets an implementation of a crptographic ... That should cover the basics of Side-channel analysis. ... Make the effect constant (constant time, constant power consumption). ...
    (sci.crypt)
  • Re: SHA-1 vs. triple-DES for password encryption?
    ... even if the attack wasn't practical. ... > somehow break MD5 that was not done since 1992? ... >>> the hash algorithms as MD5 and MD4. ... >> than you would of SHA1 to get the difficulty up to the same level. ...
    (SecProg)
  • Re: Does shuffle() produce uniform result ?
    ... one encryption key, ... cryptographic attack on the algorithms used by the driver. ... block until there's enough entropy. ...
    (comp.lang.python)
  • Re: Somebody is keep trying to ssh into my systems, how can I stop that?
    ... algorithms used in RSA. ... The RSA patent expired a couple years ... from someone who was shown to be wrong and is not man enough to admit his ... You believe HIM when he says your wrong, you attack ME when I ...
    (comp.os.linux.security)
Quantcast