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).
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).