Re: Dummy questions from a newbie

"Luca T." <lucat@xxxxxxxxxxxxx> wrote in message
news:4drqgqF1b8m1kU1@xxxxxxxxxxxxxxxxx
I have heard that to decrypt an encrypted message is hard because it is
hard to factor large numbers. In few words there is no algorithm that
does this in a reasonable amount of time. Is this true?

It is not true, the only widely used cipher that is know to be linked to
factoring is RSA. However RSA is used widely enough that most cryptosystems
in use can be broken in this way.


[Note: changes PGP to RSA so the question is reasonable]
Which one is safer/stronger? AES256 (secret key encryption) or [RSA]
(public key encryption)? And why?

For usable sizes of RSA keys AES256 will be stronger. Because RSA makes use
of keys of any size though there is a point where RSA will be harder to
break, this size though is several times larger than current keys so for the
foreseeable future AES256 will be stronger.

What is a good (reasonable) password for truecrypt (AES256)?

You'll want a passphrase with 100+ bits of entropy (256 bits of entropy
would be ideal). Diceware is the way I would go
(http://world.std.com/~reinhold/diceware.html), it is also available in
several languages so most likely your native language is available. Since
each word from diceware has almost 13-bits of entopy you'll want 8 words in
your diceware passphrase.

And which
hashing algorithm should i choose in your opinion?

Not being immediately familiar with which hashes are available in truecrypt
I will guess that SHA-256 is available. The output of this hash will match
the size of an AES256 key.

How come are you so sure that there are no mathematical Theorems (known
by NSA for instance but not by anyone else) that make factoring a joke?

I'm not, but because RSA is widely used in the banking infrastructure, and
the NSA's other task is to protect American interests, I feel it is safe to
say that if they did know such an algorithm they would be pushing everyone
away from RSA.

I know that Deep Crack did crack 56bit DES in few hours in 1997 for a
limited budget... how many bits do you believe are strong enough for
this algorithm? (For strong enough i mean that NO one on earth can
decrypt it in a reasonable amount of time)
Increasing the number of Deep Crack boards could it make it simpler to
crack DES with 128 bit or more or is it impossibile?

In theory it is possible. In reality we can simply break Deep Crack down to
it's efficiency. From memory I come up with Deep Crack performing ~900
billion operations per second. This bring 2^56 work in about 1 day. The
problem is that the work level is exponential in the key size, by this I
mean that breaking 57 bits requires twice as much work as breaking 56 bits.
As a result of this breaking 128-bits with a machine at the same scaling of
cost would require 4722366482869645213696 times the cost*time(1). Now we can
scale this based on the growth of compute power per dollar, but it's not
going to make it reasonable

Could a "Deep Crack"-like system be build to crack AES256 in weeks or
months?

Again, in theory it is possible. In reality a machine of this size would
likely require more resources than are available on the planet as it take
10^60 times the cost*time of Deep Crack. Such a device will remain
infeasible for decades if not centuries.

P.S.: Sorry if my questions are dumb.
No genuine questions are dumb, everyone started where you are now.
Joe


(1) You'll find a lot of answers given in cost*time because we can often
trade those off very easily. For example buying 2 Deep Crack machines would
cost twice as much, but perform the break in half the time.


.

Relevant Pages

  • Re: What is exponent?
    ... For simple description of RSA algorithm ... I also have the receiver's certificate (public key only). ... Use RSA to encrypt the session key ...
    (microsoft.public.dotnet.security)
  • Re: RSA Challenge Question
    ... unless the algorithm required some deep ... RSA is not used for encryption. ... *them* (Sally Jane) submit the results, wherein Chappy calls John Doe, ...
    (sci.crypt)
  • Re: Quantum slip - Quantum conspiracy
    ... RSA and DH are done in by Shor's algorithm. ... So you can look on ECC as slightly more vulnerable ... As far as NTRU goes, ...
    (sci.crypt)
  • Re: How long to break a 512 bit RSA key?
    ... That has to mean 52-bit symmetric keys, not RSA. ... Note that Deep Crack cost around $60K not counting NRE which has ... > efficient algorithms") ... access speed (it needs tons of low latency memory) than just cpu ...
    (sci.crypt)
  • Re: Large-numbers division way too slow -- what to do?
    ... > This is barrett reduction ... This is close to the technique in Paul Barett's Crypto '86 ... easier to implement than Knuth's algorithm D. ... implementation of RSA escapes me. ...
    (sci.crypt)