Interactive Python programs for demonstrating RSA encryption on graphing calculators (TI-Nspire and NumWorks): https://github.com/alexander-henkes/rsa-calculator-python

# RSA Encryption: Mathematical Implementation of a Complete Encryption Process

from math import gcd

# Prime number test
def is_prime(n):
  """Checks if a number is prime"""
  if n<2:return False  # Numbers less than 2 are not prime
  if n==2:return True  # 2 is the only even prime number
  if n%2==0:return False  # All other even numbers are not prime
  # Test only odd divisors up to the square root of n
  for i in range(3,int(n**.5)+1,2):
    if n%i==0:return False
  return True

# Prime number input with validation
def input_prime(name):
  """Prompts user to enter a prime number and validates the input"""
  while True:
    try:
      number=int(input('Prime number '+name+': '))
      if number<2:print(str(number)+' is too small!');continue
      if is_prime(number):print('Valid input: '+str(number)+' is a prime number!');return number
      else:print(str(number)+' is not a prime number!')
    except:print('Invalid input!')

# Extended Euclidean Algorithm
def extended_euclid(a,b):
  """Calculates GCD and coefficients x, y for a*x + b*y = GCD(a,b)"""
  if b==0:return a,1,0
  else:g,x1,y1=extended_euclid(b,a%b);x=y1;y=x1-a//b*y1;return g,x,y

# Calculate modular inverse
def mod_inverse(e,phi):
  """Calculates the modular inverse of e modulo phi"""
  g,x,y=extended_euclid(e,phi)
  if g!=1:return  # No inverse exists if GCD != 1
  return x%phi

# Modular exponentiation (efficient)
def power_mod(base,exponent,modulus):
  """Calculates (base^exponent) mod modulus efficiently"""
  result=1;base=base%modulus
  while exponent>0:
    if exponent%2==1:result=result*base%modulus
    exponent=exponent>>1;base=base*base%modulus
  return result

# Find suitable e
def find_e(phi):
  """Finds a suitable e that is coprime to phi"""
  candidates=[3,5,7,11,13,17,19,23,29,31]
  # Try small primes first
  for e in candidates:
    if e<phi and gcd(e,phi)==1:return e
  # If none fits, search systematically
  for e in range(2,phi):
    if gcd(e,phi)==1:return e

# Convert letter to number
def letter_to_number(letter):
  """Converts a letter to a number (A=0, B=1, ..., Z=25)"""
  letter=letter.upper()
  if'A'<=letter<='Z':return ord(letter)-ord('A')

# Convert number to letter
def number_to_letter(number):
  """Converts a number to a letter (0=A, 1=B, ..., 25=Z)"""
  if 0<=number<=25:return chr(number+ord('A'))

# Main function: RSA process
def rsa():
  # Output: Heading
  print('='*30);print('RSA Encryption');print('='*30);print()

  # STEP 1: Choose prime numbers
  print('STEP 1: Choose prime numbers');print('-'*30)
  p=input_prime('p')
  # Ensure q is different from p
  while True:
    q=input_prime('q')
    if q!=p:break
    print('Error: p and q must be')
    print('different!')
  print('Selected: p='+str(p)+', q='+str(q))
  input('Continue with Enter ...');print()

  # STEP 2: Calculate n and phi(n)
  print('STEP 2: n and phi(n)');print('-'*30)
  n=p*q  # Modulus n = p * q
  phi=(p-1)*(q-1)  # Euler function phi(n) = (p-1)*(q-1)
  print('n = p*q = '+str(p)+'*'+str(q)+' = '+str(n))
  print('phi(n) = (p-1)*(q-1)')
  print('phi(n) = '+str(p-1)+'*'+str(q-1)+' = '+str(phi))
  input('Continue with Enter ...');print()

  # STEP 3: Determine public key e
  print('STEP 3: Public key e');print('-'*30)
  print('Note: e must be coprime to')
  print('phi(n) = '+str(phi)+', i.e. (GCD(e, phi(n)) = 1)')
  suggestion=find_e(phi)
  print('Suggestion: e = '+str(suggestion))
  answer=input('Use? (Y/N): ')
  # User can accept suggestion or enter own e
  if answer.lower()=='y':e=suggestion
  else:
    while True:
      e=int(input('Use custom e: '))
      if e>=phi:print('e must be < '+str(phi)+'!');continue
      if gcd(e,phi)==1:print('Valid input:');print('GCD('+str(e)+','+str(phi)+')=1');break
      else:print('GCD('+str(e)+','+str(phi)+')!=1')
  print('Public key: ('+str(e)+', '+str(n)+')')
  input('Continue with Enter ...');print()

  # STEP 4: Calculate private key d
  print('STEP 4: Private key d');print('-'*30)
  print('d is modular inverse')
  print('of e mod phi(n)')
  print('d*e = 1 (mod '+str(phi)+')')
  print('Calculate using extended')
  print('Euclidean algorithm:')
  d=mod_inverse(e,phi)
  print('d = '+str(d))
  # Verification: d * e mod phi must equal 1
  print('Check: '+str(d)+'*'+str(e))
  print('mod '+str(phi)+' = '+str(d*e%phi))
  print('Private key: ('+str(d)+', '+str(n)+')')
  input('Continue with Enter ...');print()

  # STEP 5: Encrypt message
  print('STEP 5: Encryption');print('-'*30)
  print('Encryption: c=m^e mod n')
  print('c = m^'+str(e)+' mod '+str(n))
  print()
  print('Letter encoding:')
  print('A=0, B=1, C=2, ..., Z=25')
  print()
  # Letter input with validation
  while True:
    letter=input('Letter (A-Z): ').strip()
    if len(letter)==1:
      m=letter_to_number(letter)
      if m is not None:
        if m<n:print("'"+letter.upper()+"' = "+str(m));break
        else:print('Error: '+str(m)+' >= '+str(n));print('Choose smaller primes!')
      else:print('Invalid! Only A-Z allowed!')
    else:print('Only one letter!')
  # Perform encryption: c = m^e mod n
  c=power_mod(m,e,n)
  print()
  print('c = '+str(m)+'^'+str(e)+' mod '+str(n))
  print('c = '+str(c))
  print('Encrypted letter: '+str(c))
  input('Continue with Enter ...');print()

  # STEP 6: Decrypt message
  print('STEP 6: Decryption');print('-'*30)
  print('Decryption:')
  print('m = c^d mod n')
  print('m = '+str(c)+'^'+str(d)+' mod '+str(n))
  # Perform decryption: m = c^d mod n
  m_new=power_mod(c,d,n)
  letter_new=number_to_letter(m_new)
  print('m = '+str(c)+'^'+str(d)+' mod '+str(n))
  print('m = '+str(m_new))
  print('Decrypted letter: '+str(letter_new))
  # Verification: Does decrypted value match original?
  if m==m_new:print('Successful!')
  else:print('Error!')
  input('Continue with Enter ...');print()

# SUMMARY: Output all important values
  print('='*30);print('SUMMARY');print('='*30)
  print('Prime numbers: p='+str(p)+', q='+str(q))
  print('Modulus (p*q): n='+str(n))
  print('Euler phi function: phi='+str(phi))
  print('Public key: ('+str(e)+','+str(n)+')')
  print('Private key: ('+str(d)+','+str(n)+')')
  print('Plaintext (letter): '+letter.upper())
  print('Plaintext (number): m='+str(m))
  print('Encrypted number: c='+str(c))
  print('Decrypted number: m='+str(m_new))
  print('Decrypted letter: '+str(letter_new))
  print('='*30)

# Potential repeat loop
while True:
  rsa()  # Execute one RSA process
  print()
  again=input('Run calculation again? (Y/N): ')
  if again.lower()!='y':print('Program terminated!');break
  print('\n'*2)