Prime numbers and security

  2014-11-13

Prime numbers and security

  02:28, by Hagai Bar-El   , 607 words
Categories: Security Engineering

Without much relation to anything, I wrote this short essay about the role prime numbers play in Internet security. In a nutshell, security relies on the ability to form leverage for the defender over the adversary. Such leverage can be of one of two types:

  1. Leverage through the ability to code the system behavior.
  2. Leverage through math, where the good guy knows something that the adversary does not.

Prime numbers are used as part of at least one mathematical mechanism that serves #2.

Security is about enforcing rules on the behavior of a system, in light of an adversary wishing to break those rules. For example, the security mechanism of access control is designed to prevent a database from showing data to unauthorized people even if an unauthorized person tries to gain such access.

For the security engineer to be more powerful than the adversary in getting his own rules enforced, two types for leverage are possible. The first type is the most typical and it is leverage through the ability to code the system behavior. The programmer of the ATM gets to decide what code (logic) the ATM runs, and if he tells the ATM not to dispense cash until the current PIN was entered, and as long as the adversary has no capability to change the programmed ATM code, it works.

This type of leverage is versatile and sufficient, but is not always applicable. For example, when restricting access to data in communication it is impossible to moderate how communicated bits are processed by whoever gets to read them.

The other type of leverage is through math. Here the good guy may not have control over all aspects of the system operation, but he knows something that the adversary does not, and mathematical tricks are used to convert this unique knowledge into allowing the good guy to carry out an operation that the adversary cannot. The best example for this type of leverage is encryption. If a message is encrypted, only whoever knows the right key can decrypt and read that message, even if the system is operable by anyone.

Whereas simple types of encryption make use of Symmetric methods, that is, methods where the key used for encryption is the same one used for decryption, Asymmetric methods are also used, where encryption and decryption are carried out using mathematically related, yet different, keys. For such a mechanism to be secure, it shall be unfeasible to deduce one key from the other, unless you are the entity that made them both.

Generating a pair of keys that are mathematically related (so one decrypts what the other encrypted), while having it impossible to deduce one from the other is a difficult mathematical challenge.

Since the keys are related after all, the only way to make it impractical to deduce one from the other is to assure that such deduction requires the solution of a mathematical puzzle which is believed to be impractical to solve. One such puzzle is the breaking of a large number in a group into its prime components. When you have a modular group, and a number in it that is the product of two primes, it is believed to be impossible to deduce the prime factors without excessive work that is exponentially proportional to the size of the number. Have this number really large, and the problem is believed to be practically unsolvable.

This principle is at the heart of the RSA encryption algorithm that is used in security protocols that protect Web traffic in e-commerce and e-banking, digital signatures, and other security mechanisms to which we owe the confidentiality and integrity of our online interactions.
 

No feedback yet


Form is loading...