It’s not very often that you need to do encryption in pure Python. Obviously, you’d want to have this functionality off-loaded to C-routines whenever possible. However, in some situations, often when you require code portability or that there not be any C-compilation phase, a pure-Python implementation can be convenient.

The 25519 elliptic curve is a special curve defined by Bernstein, rather than NIST. It is fairly well-embraced as an alternative to NIST-generated curves, which are assumed to be either influenced or compromised by the NSA. See Aris’ notable 25519-patch contribution to OpenSSH.

There exists a pure-Python implementation of 25519 at this site, but it’s too expensive to use in a high-volume platform (because of the math involved). However, it’s perfect if it’s to be driven by infrequent events, and a delay of a few seconds is fine. The benefits of an EC, if you don’t already know, is that the factors are usually considerably smaller for strength comparable to traditional, non-EC algorithms. Therefore, your trade-off for a couple of more seconds of computation is an enigmatically-shorter signature.

To use it, grab the Python source, included here for posterity:

import hashlib

b = 256
q = 2**255 - 19
l = 2**252 + 27742317777372353535851937790883648493

def H(m):
  return hashlib.sha512(m).digest()

def expmod(b,e,m):
  if e == 0: return 1
  t = expmod(b,e/2,m)**2 % m
  if e & 1: t = (t*b) % m
  return t

def inv(x):
  return expmod(x,q-2,q)

d = -121665 * inv(121666)
I = expmod(2,(q-1)/4,q)

def xrecover(y):
  xx = (y*y-1) * inv(d*y*y+1)
  x = expmod(xx,(q+3)/8,q)
  if (x*x - xx) % q != 0: x = (x*I) % q
  if x % 2 != 0: x = q-x
  return x

By = 4 * inv(5)
Bx = xrecover(By)
B = [Bx % q,By % q]

def edwards(P,Q):
  x1 = P[0]
  y1 = P[1]
  x2 = Q[0]
  y2 = Q[1]
  x3 = (x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2)
  y3 = (y1*y2+x1*x2) * inv(1-d*x1*x2*y1*y2)
  return [x3 % q,y3 % q]

def scalarmult(P,e):
  if e == 0: return [0,1]
  Q = scalarmult(P,e/2)
  Q = edwards(Q,Q)
  if e & 1: Q = edwards(Q,P)
  return Q

def encodeint(y):
  bits = [(y >> i) & 1 for i in range(b)]
  return ''.join([chr(sum([bits[i * 8 + j] << j for j in range(8)])) for i in range(b/8)])

def encodepoint(P):
  x = P[0]
  y = P[1]
  bits = [(y >> i) & 1 for i in range(b - 1)] + [x & 1]
  return ''.join([chr(sum([bits[i * 8 + j] << j for j in range(8)])) for i in range(b/8)])

def bit(h,i):
  return (ord(h[i/8]) >> (i%8)) & 1

def publickey(sk):
  h = H(sk)
  a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2))
  A = scalarmult(B,a)
  return encodepoint(A)

def Hint(m):
  h = H(m)
  return sum(2**i * bit(h,i) for i in range(2*b))

def signature(m,sk,pk):
  h = H(sk)
  a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2))
  r = Hint(''.join([h[i] for i in range(b/8,b/4)]) + m)
  R = scalarmult(B,r)
  S = (r + Hint(encodepoint(R) + pk + m) * a) % l
  return encodepoint(R) + encodeint(S)

def isoncurve(P):
  x = P[0]
  y = P[1]
  return (-x*x + y*y - 1 - d*x*x*y*y) % q == 0

def decodeint(s):
  return sum(2**i * bit(s,i) for i in range(0,b))

def decodepoint(s):
  y = sum(2**i * bit(s,i) for i in range(0,b-1))
  x = xrecover(y)
  if x & 1 != bit(s,b-1): x = q-x
  P = [x,y]
  if not isoncurve(P): raise Exception("decoding point that is not on curve")
  return P

def checkvalid(s,m,pk):
  if len(s) != b/4: raise Exception("signature length is wrong")
  if len(pk) != b/8: raise Exception("public-key length is wrong")
  R = decodepoint(s[0:b/8])
  A = decodepoint(pk)
  S = decodeint(s[b/8:b/4])
  h = Hint(encodepoint(R) + pk + m)
  if scalarmult(B,S) != edwards(R,scalarmult(A,h)):
    raise Exception("signature does not pass verification")

These routines are not Python 3 compatible.

For reference, other implementations in other languages can be found at the Wikipedia page, under “External links”.

To implement the Bernstein version above, you must first generate a signing (private) key. This comes from a random 32-bit number with some bits flipped:

import os

signing_key_bytes = [ord(os.urandom(1)) for i in range(32)]

signing_key_bytes[0] &= 248
signing_key_bytes[31] &= 127
signing_key_bytes[31] |= 64

signing_key = ''.join([chr(x) for x in signing_key_bytes])

To produce the signature, and then check it:

import ed25519

message = "some data"

public_key = ed25519.publickey(signing_key)

signature = ed25519.signature(message, signing_key, public_key)
ed25519.checkvalid(signature, message, public_key)

The signing and the ensuing check take about six-seconds, together.

The ed25519 module is the one whose source is displayed above. The name “Ed25519” (the official name of the algorithm) stands for “Edwards Curve”, the mathematical foundation on which Bernstein designed the 25519 curve.