5
\$\begingroup\$

Your task is to build a function in any language that takes a message m, an encryption e, and a modulus k (all positive integers), and takes m to the power of e modulo k. Your solution must not be a theoretical one, but one that would work on a reasonable computer such as your own, for RSA keys of currently used sizes such as 2048 bits.

Shortest code wins.

\$\endgroup\$
4
  • \$\begingroup\$ How are you measuring memory usage? Does this implicitly forbid using big integer libraries unless they come with documented guarantees about their memory usage? \$\endgroup\$ Commented Feb 15, 2013 at 18:47
  • 2
    \$\begingroup\$ (And if you're going to post a challenge about RSA, why not make it interesting by asking for an implementation of real RSA as opposed to academic useless-for-protecting-secrets RSA?) \$\endgroup\$ Commented Feb 15, 2013 at 18:48
  • \$\begingroup\$ @PeterTaylor: Big-integer libraries are fine. The main point of the limit is to prevent people from trying to store the entire exponentiated number and then evaluating it modulo m. \$\endgroup\$
    – Joe Z.
    Commented Feb 15, 2013 at 18:50
  • \$\begingroup\$ @PeterTaylor: Also, you can pose the question that includes PKCS #1 if you want. \$\endgroup\$
    – Joe Z.
    Commented Feb 15, 2013 at 18:53

5 Answers 5

6
\$\begingroup\$

Python – 5

Python 3 built-in function pow have third parameter. So Python 3 already have built-in RSA encoder

r=pow
\$\endgroup\$
5
  • \$\begingroup\$ Looks like we have a winner. I didn't know that. :\ \$\endgroup\$
    – Joe Z.
    Commented Feb 23, 2013 at 20:20
  • \$\begingroup\$ In fact, the solution has a length of 0. Just use function pow for RSA encoding/decoding \$\endgroup\$
    – AMK
    Commented Feb 23, 2013 at 20:33
  • \$\begingroup\$ Nope, it's still length 3 because you need to describe it. :P \$\endgroup\$
    – Joe Z.
    Commented Feb 23, 2013 at 20:34
  • 1
    \$\begingroup\$ Imho, this solution has a char count of 5. By just providing pow, the criteria 'build a function' is not satisfied. \$\endgroup\$
    – codeporn
    Commented Feb 25, 2013 at 11:16
  • \$\begingroup\$ Yeah, I suppose that's true. \$\endgroup\$
    – Joe Z.
    Commented Feb 27, 2013 at 13:38
1
\$\begingroup\$

Here's my first attempt at actually golfing something here:

Python – 69 61 55

r=lambda m,e,k:1 if e==0 else m**(e%2)*r(m*m%k,e/2,k)%k

This is a simple exponentiation by squaring algorithm.


02/15 13:17 – 61: Used lambda notation.
02/22 15:44 – 55: Removed some brackets as per grc's suggestions.

\$\endgroup\$
9
  • \$\begingroup\$ I believe the question specifies that the function should be named RSA \$\endgroup\$
    – Shmiddty
    Commented Feb 15, 2013 at 17:50
  • \$\begingroup\$ Sorry, that was unclear on my part. \$\endgroup\$
    – Joe Z.
    Commented Feb 15, 2013 at 18:11
  • 1
    \$\begingroup\$ You can save a few chars by removing unnecessary spaces and brackets: r=lambda m,e,k:1if e==0 else m**(e%2)*r(m*m%k,e/2,k)%k. And you might also be able to do this, but I haven't tested it: r=lambda m,e,k:e<1or m**(e%2)*r(m*m%k,e/2,k)%k. It uses e<1 instead of e==0 and or instead of if ... else. \$\endgroup\$
    – grc
    Commented Feb 16, 2013 at 0:30
  • 1
    \$\begingroup\$ In most C-derived languages, */% have equal precedence and are evaluated left-to-right. \$\endgroup\$ Commented Feb 22, 2013 at 20:59
  • 1
    \$\begingroup\$ @Joe Zeng: Yes, but True behaves as 1 when it is used with arithmetic operators. \$\endgroup\$
    – grc
    Commented Feb 23, 2013 at 0:45
0
\$\begingroup\$

java (83 chars)

if input is of BigInteger type:

public BigInteger r(BigInteger m,BigInteger e,BigInteger k){return m.modPow(e,k);}
\$\endgroup\$
0
\$\begingroup\$

Husk, 7 bytes

!¡o%⁰*³

Try it online!

Function that takes arguments: arg1=m (message), arg2=k (key/modulus), arg3=e (exponent/encryption).

Encoding takes about 10 seconds on [Try it online!] with a message of 12345678910, a 2048-bit key/modulus of 17335246217810680499565282364130282347913694411139706552337646969996795185310539972695213589521948877888710148108314183322475193115466538523720272848165926667358225384343389288464059692412384746831929390686202279817642231618920311152771862965772849228722380926373552800043250590230507345247504584516585217552163181827225685419709962073929610117852078754818132187957128758451536498778247147713136878727238232838512570562685513074673965992921930197584545660069134797478016576085619884280636191861425890311213983668804147423192923778212236303196414996652277121672303217925415867248268691221399027188630076689585126618899, and exponent/encryption of 65537.

Decoding is significantly longer when (as is usual) the decryption exponent d is much larger than the encryption exponent e. But we can check that it works using small values: m=123, k=257 and e=7 (for which the decryption exponent d=55):
Try encoding
Try decoding

\$\endgroup\$
0
\$\begingroup\$

Nibbles, 4 bytes (8 nibbles)

=_`.@%*_
=_`.@%*_        # full program
=_`.@%*_$@      # with implicit args added
  `.            # repeatedly apply (while results are unique)
    @           # starting with arg2:
      *_$       #   multiply arg2 by result-so-far
     %   @      #   and modulo by arg1
=_              # finally, return result at index given by arg3

Full program that takes arguments: arg1=k (key/modulus), arg2=m (message), arg3=e (exponent/encryption).

Encoding is fast (screenshot below shows a message of 12345678910, a 2048-bit key/modulus, and exponent/encryption of 65537).
enter image description here Decoding is significantly longer when (as is usual) the decryption exponent d is much larger than the encryption exponent e. But we can check that it works using small values: m=123, k=257 and e=7 (for which the decryption exponent d=55). enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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