For more details, I should refer you to a brilliant answer on cryptography.SE (go and upvote :-)).įinally, in order to have a trapdoor, N is built so as to be a composite number. The sizes of the modulus which are recommended (2048 bits, or 617 decimal digits) relate to the availability of computation power at present time, so that if you stick to them you are assured that it will be extremely expensive for the attacker to break it.
Of course, "hard" does not mean that it is always hard, but (intuitively) that increasing the size of N by a certain factor increases the complexity by a much larger factor.
The "hard" problem is to find the e-th root of C (that is, M). In the case of RSA, the "easy" function is the modular exponentiation C = M e mod N where the factors of N are kept secret. "Hard" very often refers to computations that cannot be solved in polynomial time O(n x) for some fixed x and where n is the input data. "Easy" and "hard" are just qualitative adjectives that are always more formally defined in terms of computational complexity. All public key algorithms are based on trapdoor functions, that is, mathematical constructs that are "easy" to compute in one way, but "hard" to reverse unless you have also some additional information (used as private key) at which point also the reverse becomes "easy".
0 kommentar(er)
