Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Why does RSA use fixed-point numbers instead of floating-point? Are there too many floating-point implementations to choose from? Does fixed-point arithmetic increase the difficulty of factorization? Or is it something else?

Wouldn't the extra complexity of floating-point increase the security of the algorithm?

share|improve this question
    
RSA uses integers, not fixed point. (Unless you see integers as special case of fixed point, but that's not an enlightening view in this context). –  CodesInChaos May 2 '13 at 12:27
    
Why not? Implementation-wise integers are a case of fixed point numbers. –  muma May 2 '13 at 12:44
5  
Complexity != security. Complexity for the sake of being complex is BAD. –  Jonathan Garber May 2 '13 at 13:00

2 Answers 2

up vote 4 down vote accepted

Why is RSA using fixed point type numbers?

Technically speaking, RSA operates on residue classes which are equivalence classes, with the definition "two integers are equivalent" being "they share the same remainder".

These classes are populated only by integers, so the RSA operation has no need of floating point storage types. As such, it does not make sense to waste space sorting an exponent, as it is not needed - even large integers can be stored in memory using an arbitrary precision arithmetic library - if for example you split the integer up into 32-bit chunks, or four bytes, you only need 128 4-byte chunks to store that integer, or 512 bytes.

Is it because only the fixed point arithmetics provide the difficulties of factorization?

Factorisation gets more complicated when you start defining other sets. For example, under some constructions a number can be irreducible, but not prime.

Since RSA works very well under the simplest of sets we know and understand, the integers, there is little point introducing additional complexity unless we need it.

share|improve this answer
    
Would it be feasible, in the sense of increasing the security, to adapt the algorithm in the future? When - let's say - quantum computers or comparable efficient systems are broadly used? Or would the adaption be unwise in any sense? –  muma May 2 '13 at 12:42
    
@muma The "conditions" if you like that make primes so useful only apply in certain cases. The class of cases in which this is valid are called principal ideal domains, the simplest of which is the integers. Since rationals and reals are a field, it would work, but the case for a set of fractions would be identical to an integer case, the link between them being multiplying through by the denominator. So you'd not gain a lot. –  user2213 May 2 '13 at 13:08
    
Of course! Sorry, my math-days are to long ago. Didn't think that through. –  muma May 2 '13 at 13:22
    
@muma it's actually very complicated - some of the non-easy PIDs can get very confusing. I had to read it through several times before I posted that comment! –  user2213 May 2 '13 at 13:25

Floating point numbers are approximation of real numbers. They are appropriate for continuous computations, where a small variation of the input results in a small variation of the output.

Cryptography generally involves computations that are as far as it gets from continuous. No matter how similar two non-identical messages are, they should not have similar hashes, or similar signatures, or similar encryptions. Floating point are wholly inappropriate for this.

Cryptography often involves some kind of irreversible-looking scrambling, which you can only reverse given a secret key (or not at all). Natural processes tend to be continuous, hence reversible. Chaotic processes, whose past cannot be computed, tend to involve integers at some point — often a number of iterations or loops, where a threshold is hit or missed at each iteration. Integers are the way the irreversibility arises.

The result of cryptographic operations has to be reproducible. For example, the decryption process has to exactly reverse the encryption process. Floating point numbers are at a disadvantage there because operations on them tend to have variations among different processor architectures.

A lot of cryptography, including RSA, relies on “nice” properties of integers, often related to divisibility (which is fundamentally a property of integers). Floating point numbers have no such properties that make the algorithms work.

Complexity is not what makes cryptographic algorithms secure. It's a combination of mathematical properties, and of nobody having found a way to break them. There is absolutely nothing to be gained with floating point computations there, and as we've seen a lot to lose.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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