AES and Symmetric vs Asymmetric key length

2 views
Skip to first unread message

David Crick

unread,
Nov 11, 1998, 3:00:00 AM11/11/98
to
Hi,

It has been quoted that a 128-bit symmetric key (eg for IDEA) is
equivalent in length to a ~3000-bit asymmetric key (eg for RSA).

With AES offering up to 256-bit key length, what size [RSA]
public key would be required to maintain the same strength?

In a related matter, with ECC keys being considerably smaller
than RSA keys for the same security (I'm right here, aren't I?),
would it then be wise to move to ECC for the PKC method? What
length ECC key would we need?

Finally, am I right in thinking that RSA and the PGP5/6 public
key methods (I think they're referred to D-H but are actually
Elgamal?) have the same security for the same length?

Thanks,

David.

--
+---------------------------------------------------------------------+
| David Crick dac...@mcmail.com http://members.tripod.com/~vidcad/ |
| Damon Hill WC '96 Tribute: http://www.geocities.com/MotorCity/4236/ |
| Brundle Quotes Page: http://members.tripod.com/~vidcad/martin_b.htm |
| PGP Public Key: (RSA) 0x22D5C7A9 00252D3E4FDECAB3 F9842264F64303EC |
+---------------------------------------------------------------------+

Bruce Schneier

unread,
Nov 11, 1998, 3:00:00 AM11/11/98
to
On Wed, 11 Nov 1998 18:50:54 +0000, David Crick <dac...@mcmail.com>
wrote:

>Hi,
>
>It has been quoted that a 128-bit symmetric key (eg for IDEA) is
>equivalent in length to a ~3000-bit asymmetric key (eg for RSA).
>
>With AES offering up to 256-bit key length, what size [RSA]
>public key would be required to maintain the same strength?

Being someone who put a table of comparisons in my book, I should say
something here. I don't think comparison tables are valid, in
general, and have to be made specific to the appication. The threat
model is different. In PGP, for example, breaking the symmetric
algorithm yields one message. Breaking the public-key algorithm
yields all messages. How do you compare relative strengths there?

Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com

Medical Electronics Lab

unread,
Nov 12, 1998, 3:00:00 AM11/12/98
to
Bruce Schneier wrote:
>
> On Wed, 11 Nov 1998 18:50:54 +0000, David Crick <dac...@mcmail.com>
> wrote:
> Being someone who put a table of comparisons in my book, I should say
> something here. I don't think comparison tables are valid, in
> general, and have to be made specific to the appication. The threat
> model is different. In PGP, for example, breaking the symmetric
> algorithm yields one message. Breaking the public-key algorithm
> yields all messages. How do you compare relative strengths there?

Relative importance is different from relative strength. It's
obviously worth more to crack the PK than the symmetric in that
instance independent of relative strength.

It's not possible to do a concrete comparison, but we can do a
"fuzzy" comparison that has the correct order of magnitude. Basicly,
we can compare the number of operations and make some kind of
assumption about the time it takes to perform an operation. For
a symmetric key, the number of operations to brute force a key
is about 2^(n-1). For an RSA key it's on the order of
exp(c(log log n)^2/3 (log n)^1/3) and for ECC keys its on the
order of 2^(n/2).

That kind of answers the question about relative strength, but
can not address the problem of relative importance. The
security of a system has nothing to do with the crypto and
everything to do with how you use the crypto. Understanding
the difference in bit length is useful, but be really careful
how you use the knowledge.

Patience, persistence, truth,
Dr. mike

Thomas J. Boschloo

unread,
Nov 14, 1998, 3:00:00 AM11/14/98
to
Bruce Schneier wrote:

> Being someone who put a table of comparisons in my book, I should say
> something here. I don't think comparison tables are valid, in
> general, and have to be made specific to the appication. The threat
> model is different. In PGP, for example, breaking the symmetric
> algorithm yields one message. Breaking the public-key algorithm
> yields all messages. How do you compare relative strengths there?

How many vital encrypted messages do you exchange during your lifetime?
If you assume 1000, substract ten bits from the symetric keysize ;-) I
wouldn't notice the difference between 128 and 118 bit encryption..

Thomas Boschloo

--
"Governments control our lives, but who controls our governments" - Me

Email: lastnameatmultiwebdotnl
PGPkey: http://x13.dejanews.com/getdoc.xp?AN=406702465

Thomas J. Boschloo

unread,
Nov 14, 1998, 3:00:00 AM11/14/98
to
-----BEGIN PGP SIGNED MESSAGE-----

Medical Electronics Lab wrote:

> It's not possible to do a concrete comparison, but we can do a
> "fuzzy" comparison that has the correct order of magnitude. Basicly,
> we can compare the number of operations and make some kind of
> assumption about the time it takes to perform an operation. For
> a symmetric key, the number of operations to brute force a key
> is about 2^(n-1). For an RSA key it's on the order of
> exp(c(log log n)^2/3 (log n)^1/3) and for ECC keys its on the
> order of 2^(n/2).

So call me a math inapt, but how do I put these formula's in a spread
sheet? I don't know what to do with the 'c' in 'exp(c(log(log(n))^(2/3)
...)'. Let's assume one round of RSA takes as long as IDEA on a special
purpose machine.

Thanx in advance,
Thomas Boschloo
-----BEGIN PGP SIGNATURE-----
iQB5AwUBNk2UtwEP2l8iXKAJAQGr7wMfaIZZIK65ViqkkR+uMhc+4ZSFnLtSCITp
0+ykZul/T2df9LSkQIYJd7oMctprlOg7K5letHZ0BVsR6ZYRRTNlxGUbx4e2vYqK
JFfGg++l9UBaA7+Od159JvXrr4r4pnZEY6UVZA==
=E+Qg
-----END PGP SIGNATURE-----

Your Name

unread,
Nov 16, 1998, 3:00:00 AM11/16/98
to
In article <364DA2D0.95C59393@-.->, -@-.- says...
c is probably a positive constant so let c = 1

In fact, that same equation, exp((ln k)^1/3 * (ln(ln k))^2/3) ,
is in Schneier's book and is described as a good approximation
to the number of operations required to factor an integer k
useing the number field sieve algorithm.

He defines an operation as a complex iteration of the algorithm,
not a simple microcomputer operation. To calculate a specific
time, he uses the constant of one million operations per second.

If you want to calculate the number of operations required to
factor a decimal integer k with d digits, set k = 10^d or
(10^d)-1 and plug it in. For a 250 digit base 10 integer,
let k = 10^250

For a base 2 integer with d digits, set k = 2^d or (2^d)-1
Example: to test a 1000 bit integer, let k = 2^1000

That would be my guess.

Rich E. aka freemanatshoredotnet

Medical Electronics Lab

unread,
Nov 16, 1998, 3:00:00 AM11/16/98
to
Your Name wrote:
> >Medical Electronics Lab wrote:
> >
> >> It's not possible to do a concrete comparison, but we can do a
> >> "fuzzy" comparison that has the correct order of magnitude. Basicly,
> >> we can compare the number of operations and make some kind of
> >> assumption about the time it takes to perform an operation. For
> >> a symmetric key, the number of operations to brute force a key
> >> is about 2^(n-1). For an RSA key it's on the order of
> >> exp(c(log log n)^2/3 (log n)^1/3) and for ECC keys its on the
> >> order of 2^(n/2).

I wrote the above, your program missed a > !

> >So call me a math inapt, but how do I put these formula's in a spread
> >sheet? I don't know what to do with the 'c' in 'exp(c(log(log(n))^(2/3)
> >...)'. Let's assume one round of RSA takes as long as IDEA on a special
> >purpose machine.
> >
> >Thanx in advance,
> >Thomas Boschloo

RSA doesn't have rounds. That's why these comparisons are fuzzy.
Block ciphers avoid math so they can't be easily cracked, key
sharing routines use lots of math so they can ensure the level
of security. The fuzzy test I mentioned compares the sweetness
of apples and cantalopes, you can tell which is spoiled but you
can't compare the taste.

> c is probably a positive constant so let c = 1

correct. Ranges from 1.0xx up to 3.xx depending on several things.
Assuming 1 for this test is close enough.

>
> In fact, that same equation, exp((ln k)^1/3 * (ln(ln k))^2/3) ,
> is in Schneier's book and is described as a good approximation
> to the number of operations required to factor an integer k
> useing the number field sieve algorithm.
>
> He defines an operation as a complex iteration of the algorithm,
> not a simple microcomputer operation. To calculate a specific
> time, he uses the constant of one million operations per second.
>
> If you want to calculate the number of operations required to
> factor a decimal integer k with d digits, set k = 10^d or
> (10^d)-1 and plug it in. For a 250 digit base 10 integer,
> let k = 10^250

Right. log k = 250 and log(log k) is the number of digits in k = 8

>
> For a base 2 integer with d digits, set k = 2^d or (2^d)-1
> Example: to test a 1000 bit integer, let k = 2^1000
>
> That would be my guess.

Yup. The basic idea is that you can *roughly* compare the number
of bits needed in a type of cipher to make the attackers choice
of attack independent of the work effort. For example, if you
use a 128 bit symmetric key, you would want to use at least 260
bits of ECC key to protect it with the same level of security.
That ignores the actual time it takes to compute either the
symmetric algorithm or the ECC version, symmetric systems are
usually much faster. To protect a 128 bit key using an IF scheme
(integer factorization) it's more like 3000 bits.

These numbers are fuzzy, they give you an order of magnitude
estimate which can help make design decisions. They can not,
and should not be used to make comparisons between ciphers.
Apples are not cantalopes! They both taste good though :-)

Thomas J. Boschloo

unread,
Nov 17, 1998, 3:00:00 AM11/17/98
to
-----BEGIN PGP SIGNED MESSAGE-----

Thomas J. Boschloo wrote:

> Bruce Schneier wrote:
>
> > Being someone who put a table of comparisons in my book, I should say
> > something here. I don't think comparison tables are valid, in
> > general, and have to be made specific to the appication. The threat
> > model is different. In PGP, for example, breaking the symmetric
> > algorithm yields one message. Breaking the public-key algorithm
> > yields all messages. How do you compare relative strengths there?
>
> How many vital encrypted messages do you exchange during your lifetime?
> If you assume 1000, substract ten bits from the symetric keysize ;-) I
> wouldn't notice the difference between 128 and 118 bit encryption..
>
> Thomas Boschloo

Maybe this post was as 'uninformed' as my other post about the strength
of n bit RSA :-( I wanted to add that remailers will process many more
vital messages during their life time as a normal user like me would. So
comparing the two like I suggested would be better left to the user!

For information about anonymous remailing, try
<http://anon.efga.org/~rlist/> or <news:alt.privacy.anon-server>. Their
keys are mostly 1024 or 2048 bit RSA (let's hope that is enough).

You could also try the HTML Mixmaster form at <http://www.replay.com/>
or send a message with subject: remailer-help, to
rema...@base.xs4all.nl.

Thomas
-----BEGIN PGP SIGNATURE-----
iQB5AwUBNlEbegEP2l8iXKAJAQH32QMgsVR5W1iCX4iQIwQfpsAee3Ldxno2Xxvj
/aziL+SOcgS8yQjvykyEQx4/SlQQvc5fdDqKo4lE7VpGEjneF9Q2vegy9ExWss8b
JGytBxU43te01OfMg2ABBWn7chfHWSis1HVczQ==
=WULI

Reply all
Reply to author
Forward
0 new messages