4
$\begingroup$

This is a theoretical question to solve an argument with a friend..

Is there a working cryptographic system that do square root operations during the encryption process?

"Working" means that it is really implemented, and not just an academic research.

Hint: I suspect that it is not possible as computer hardware has floating point limitations as it is based on binary, causing infinitely small numbers to truncate, hence doing sqrt during encryption loses information, and cannot be undone during the decryption.

Please help me win the bet :)

$\endgroup$
  • 9
    $\begingroup$ You can definitely use non-reversible functions to construct reversible ones, e.g. in a Feistel cipher. Also, if square roots in a finite field count, those can be reversible. (Also, the Rabin cryptosystem probably merits at least a passing mention, even though it only requires computing (modular) square roots for decryption, not for encryption.) $\endgroup$ – Ilmari Karonen Apr 8 '19 at 14:53
  • $\begingroup$ There's some relevant rounding stuff at Could there be a floating point CSPRNG? $\endgroup$ – Paul Uszak Apr 8 '19 at 15:05
  • 2
    $\begingroup$ The initialization vectors of the SHA-2 functions are the binary expansions of the fractional parts of the (real number) square roots of small prime numbers. The SHA-2 functions are often used with encryption, e.g. in a key derivation function for a public-key encryption scheme. Does that count? $\endgroup$ – Squeamish Ossifrage Apr 8 '19 at 15:39
  • 2
    $\begingroup$ Actually, if your CPU does IEEE math (universal nowadays), that places very strict requirements on the accuracy of the floating sqrt operation. Of course, you still have to account for the varying degrees of precision that various implementations provide, but it would be possible (however, I haven't heard of anyone actually doing it) $\endgroup$ – poncho Apr 8 '19 at 15:49
  • $\begingroup$ I think there's also some cipher that uses the middle square method for diffusion, but I forget if it was a block cipher or stream cipher or hash. Granted, squaring is not the same as taking a square root, but still. $\endgroup$ – forest Apr 9 '19 at 23:04
5
$\begingroup$

I'm not aware of any cipher which uses square root as a primitive operation, and I suspect that none exist. Cipher designers tend to prefer a large number of simple operations to a lesser number of complex ones. The most complex operation used in practice is multiplication, and even that is not extremely common. The most complex mathematical operations I know of used in a cipher are exponentiation and logarithms. From a quote by James Massey on the use of complex functions:

I have many times used the discrete exponential or the discrete logarithm as nonlinear cryptographic functions and they have never let me down.


There is no reason why a square root operation would need to return a floating point value (for example, in 8-bit integer arithmetic, $\sqrt50=7$, though it's likely that taking the fractional part of the square root would be more beneficial for causing diffusion and promoting nonlinearity), so it is possible to use, technically. It's perfectly possible to return an integer and still achieve diffusion. I have a few guesses as to why no cipher uses square roots as a cryptographic mixing operation:

  • It's difficult to write a fast constant time implementation, which is necessary to avoid side-channels.

  • The nonlinear properties it provides are not well-researched compared to other operations.

  • It is a complex and slow function, and cryptographers often prefer many simple and fast functions.

  • Unless done in a finite field, it is impossible to reverse the operation (which is often useful).


If you loosen your requirements, then the Rabin cryptosystem may fit the bill. It's an asymmetric cipher and is very similar to RSA, but with the public exponent fixed to $2$. This means that decryption involves computing modular square roots. It's very possible that there is other asymmetric cryptography which makes use of square root operations, but I can't think of any off the top of my head.

If you can expand your requirements to any $n^\text{th}$-root operations, then the broken KN-Cipher from 1995 may be relevant. Its round function is based on the cube root operation in $\operatorname{GF}(2^{33})$. Computing cube roots is also a simpler and faster process than computing square roots.

$\endgroup$
  • $\begingroup$ Nothing inherently wrong with floating-point sqrt as a reliably computed function from bit strings to bit strings! It's one of the mandatory correctly rounded IEEE 754 operations. (But its cryptographic value is limited.) $\endgroup$ – Squeamish Ossifrage Apr 8 '19 at 19:21
  • $\begingroup$ Yes of course and there is no "decryption" by square roots :-) $\endgroup$ – kodlu Apr 8 '19 at 20:31
  • $\begingroup$ Whilst $\sqrt{50}=7$ in your 8 bits is a lucky guess, IEEE 754 bus widths mean that $\sqrt{x}_8 \ne \sqrt{x}_{64}$ for $\forall x$. $\endgroup$ – Paul Uszak Apr 9 '19 at 0:18
  • 2
    $\begingroup$ @PaulUszak I'm not talking about IEEE floating point. And your statement is incorrect. $\forall x$ means for all $x$, but it's easy to create an $x$ whose square root is the same regardless of the bus width (e.g. $x=64$). $\endgroup$ – forest Apr 9 '19 at 0:19
  • $\begingroup$ Well spotted - lazy copy & paste. $\endgroup$ – Paul Uszak Apr 9 '19 at 0:27
-3
$\begingroup$

The reason this can't generally work is illustrated with this code example:-

 double root = 101;
 for (int i = 0; i < 10; i++){
   root = sqrt(root);
 }
 println(root);

For current 8 bit Atmel hardware, root = 1.004517078399658203125.

For current 32 bit Xtensa hardware, root = 1.0045171252204596612500608898699283599853515625.

For current 64 bit Intel hardware, root = 1.0045171252204597.

A Commodore 64 might produce yet different results.

The numbers diverge after only the 6th decimal place in the worst case. I used 10 'rounds'. Cipher SIMON can use up to 72. IEEE 754 has little relevance in the general case for comparing multiple floating point operations as the overriding factor is bus width. So do we then truncate? If so where? Unfortunately, the gaps between the residual numbers would be different, even within the same bus width as shown below:-

gaps

This graph (logarithmic) means that something as simple as counting in steps of 0.1 is non linear when considering active bits. And the converse is also true in that 1 bit increments produce non linear numeric increments. This also means that different hardware would produce different results as $\sqrt{x}$ approached IEEE 754 bit boundaries. There are many $x$ where $ \sqrt{x}_8 \ne \sqrt{x}_{64} $.

IEEE 754 reflects the bus width, so the accuracy changes depending on the hardware. For inexplicable reasons cryptographers prefer a one size fits all kit approach so it wouldn't be possible to encrypt with one bus width, and decrypt with another bus width. Consequently it would all be very tricky.


However for interest, see https://crypto.stackexchange.com/a/48658/23115 which shows how $\sqrt{57} \equiv \{71,18\} \bmod 89$ in elliptic curve theory. That seems to manage rooting strictly within the integers, bypassing IEEE 754 and it's rounding problems. But this isn't a cipher.

$\endgroup$
  • $\begingroup$ Why exactly would you use floating point arithmetic...? Also you're using "non-linear" wrong. $\endgroup$ – forest Apr 8 '19 at 23:48
  • 1
    $\begingroup$ I'm not sure why it would be tricky. It would be more simple than using IEEE floating point. Just look at how the SAFER family of ciphers does it with discrete exponentiation and the like. It wasn't tricky there. $\endgroup$ – forest Apr 9 '19 at 0:26
  • 3
    $\begingroup$ IEEE 754 semantics has nothing to do with bus width of a physical hardware design. Certainly certain hardware designs are more efficient but the question wasn't about efficiency of numerical computation on your microcontroller; the question was about cryptography. $\endgroup$ – Squeamish Ossifrage Apr 9 '19 at 1:39
  • 2
    $\begingroup$ I guess it's not possible to evaluate a 128-bit block cipher like AES on my 64-bit x86 CPU, then, huh? Better switch everything to Blowfish! (The word ‘bus’ does not appear in IEEE 754-1985 or IEEE 754-2008. This standard which you seem to have read very carefully sure is loquacious on the topic of bus widths and hardware designs. Certainly the opening paragraph doesn't say anything about whether it can be implemented in software, hardware, or a combination of the two, does it?) $\endgroup$ – Squeamish Ossifrage Apr 9 '19 at 14:15
  • 3
    $\begingroup$ 1.0045171252204596612500608898699283599853515625 and 1.0045171252204597 are representations of equivalent double values. Both decimal values round to the same 64-bit floating point value. The difference is not that the two computers computed different values. One programming environment just printed a different number of digits than the other. Neither is wrong. $\endgroup$ – Future Security Apr 9 '19 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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