RSA Ontology

FLOW ALGEBRA
TITLE: RSA Ontology
DOMAIN: Discrete Mathematics / Cryptography
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/cryptography/rsa-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Mathematical synthesis; live page not independently verified.

FLOW "RSAOntology" v1.0

# PURPOSE
Represent RSA as a typed, verifiable public-key cryptographic construction,
separating mathematical correctness from practical security guarantees.

ENTITY_TYPES:
  Integer: Z
  PositiveInteger: {n in Z | n > 0}
  Prime: {p in Z | p > 1 and prime(p)}
  Modulus: PositiveInteger
  PublicExponent: PositiveInteger
  PrivateExponent: PositiveInteger
  PublicKey: (n:Modulus, e:PublicExponent)
  PrivateKey: (n:Modulus, d:PrivateExponent, optional_crt_parameters)
  MessageRepresentative: Integer
  CiphertextRepresentative: Integer
  EncodedMessage: ByteString
  Signature: ByteString
  PaddingScheme: {OAEP, PSS, legacy_PKCS1_v1_5}
  HashAlgorithm: AlgorithmIdentifier
  KeyPair: (public:PublicKey, private:PrivateKey)

RELATIONSHIPS:
  RSA IS_A asymmetric_public_key_cryptosystem
  RSA USES modular_exponentiation
  RSA USES prime_factorisation_hardness_assumption
  PublicKey CORRESPONDS_TO PrivateKey
  Modulus DERIVED_FROM two_distinct_primes
  Encryption REQUIRES public_key
  Decryption REQUIRES private_key
  Signing REQUIRES private_key
  Verification REQUIRES public_key
  OAEP PROVIDES probabilistic_encryption_encoding
  PSS PROVIDES probabilistic_signature_encoding

# KEY GENERATION (mathematical core)
INPUT: distinct primes p, q
PRECONDITIONS: p != q; prime(p); prime(q)
n := p*q
lambda_n := lcm(p-1, q-1)
CHOOSE e such that 1 < e < lambda_n and gcd(e,lambda_n) = 1
d := inverse_mod(e,lambda_n)
OUTPUT: public_key=(n,e); private_key=(n,d)
INVARIANTS:
  n = p*q
  (e*d) mod lambda_n = 1
  gcd(e,lambda_n) = 1
  d exists uniquely modulo lambda_n
SECURITY_NOTE: Production implementations require approved key sizes,
cryptographically secure prime generation, side-channel protections,
and secure key handling.

# RAW RSA PRIMITIVES (NOT SECURE APPLICATION PROTOCOLS)
RSAEP((n,e), m):
  require 0 <= m < n
  return pow_mod(m,e,n)
RSADP((n,d), c):
  require 0 <= c < n
  return pow_mod(c,d,n)
CORRECTNESS:
  RSADP(private_key, RSAEP(public_key,m)) = m for 0 <= m < n
  provided keys are valid as above.
WARNING: Textbook/raw RSA is deterministic and must not be used directly
for confidentiality, signatures, or arbitrary message bytes.

# SECURE ENCRYPTION WORKFLOW
RSA_OAEP_ENCRYPT(public_key, message, label, randomness):
  encoded := OAEP_ENCODE(message, modulus_octet_length, label, randomness)
  require encoded fits modulus and OAEP message length bounds
  return I2OSP(RSAEP(public_key, OS2IP(encoded)), modulus_octet_length)
RSA_OAEP_DECRYPT(private_key, ciphertext, label):
  representative := OS2IP(ciphertext)
  encoded := I2OSP(RSADP(private_key, representative), modulus_octet_length)
  return OAEP_DECODE_OR_FAILURE(encoded, label)
SECURITY_NOTE: OAEP encoding must be validated in full; decoding failure
must not leak sensitive information through error or timing differences.

# SECURE SIGNATURE WORKFLOW
RSA_PSS_SIGN(private_key, message, hash_algorithm, randomness):
  encoded := PSS_ENCODE(hash_algorithm(message), modulus_bit_length-1, randomness)
  signature_rep := RSASP1(private_key, OS2IP(encoded))
  return I2OSP(signature_rep, modulus_octet_length)
RSA_PSS_VERIFY(public_key, message, signature, hash_algorithm):
  require signature has required length and representative < n
  encoded_rep := RSAVP1(public_key, OS2IP(signature))
  encoded := I2OSP(encoded_rep, ceil((modulus_bit_length-1)/8))
  return PSS_VERIFY_ENCODING(hash_algorithm(message), encoded)
SECURITY_NOTE: Signature verification establishes validity under the
supplied public key, not the real-world identity of the key owner.

# MATHEMATICAL LAWS
LAW modular_exponentiation: pow_mod(a,b,n) = (a^b) mod n
LAW key_inverse: e*d = 1 (mod lambda(n))
LAW gcd_condition: gcd(e,lambda(n)) = 1
LAW rsa_round_trip: (m^e)^d mod n = m for 0 <= m < n
LAW crt_reconstruction: x mod p and x mod q uniquely determine x mod (p*q)
LAW factorisation: n = p*q with p and q distinct primes

# INFERENCE RULES
RULE valid_keypair:
  IF distinct_primes(p,q) AND n=p*q AND gcd(e,lcm(p-1,q-1))=1
     AND e*d mod lcm(p-1,q-1)=1
  THEN rsa_keypair_mathematically_valid(n,e,d)
RULE decrypt_correct:
  IF rsa_keypair_mathematically_valid(n,e,d) AND 0<=m<n
  THEN pow_mod(pow_mod(m,e,n),d,n)=m
RULE verify_pss:
  IF rsa_pss_verification_succeeds(public_key,message,signature)
  THEN signature_valid_for_supplied_public_key
RULE no_identity_inference:
  IF signature_valid_for_supplied_public_key
  THEN NOT_AUTOMATICALLY identity_of_key_owner_authenticated
RULE no_raw_security_inference:
  IF raw_rsa_round_trip_correct
  THEN NOT_AUTOMATICALLY semantically_secure_encryption

# VALIDATION
CHECK primality_of_p_and_q
CHECK p_not_equal_q
CHECK modulus_equals_product
CHECK public_exponent_range_and_coprimality
CHECK private_exponent_modular_inverse
CHECK representative_ranges
CHECK oaep_pss_encoding_and_parameter_compatibility
CHECK secure_randomness_and_key_protection
CHECK no_unsupported_claims_about_security
CHECK separate_encryption_and_signature_key_usage_by_policy
CHECK malformed_ciphertexts_and_signatures_fail_safely

# SEMANTIC_EQUIVALENCE
RSA public exponentiation ~= modular exponentiation with public exponent
RSA private exponentiation ~= modular exponentiation with private exponent
RSA-OAEP != textbook RSA
RSA-PSS != RSA encryption
Public key verification != independent identity certification
Mathematical correctness != implementation security

# CONFIDENCE
formal_mathematical_definitions: 0.99
rsa_round_trip_under_valid_keys: 0.99
practical_security_claims: conditional_on_parameters_implementation_and_threat_model
source_page_alignment: unverified

# FLOW_HASH
method: SHA-256
input: canonical_UTF8_serialisation_of_flow_excluding_FLOW_HASH_value
value: compute_on_publication

# UPDATE_MODEL
triggers:
  - cryptographic_standard_revision
  - algorithm_or_padding_deprecation
  - new_cryptanalysis_or_security_guidance
  - source_page_revision
policy: review_version_validate_rehash_republish

# AI_CONSUMPTION
mode: typed_semantic_knowledge
retrieval_keys: [RSA, public-key cryptography, modulus, public exponent,
  private exponent, modular arithmetic, OAEP, PSS, digital signature]
reasoning_constraints:
  - preserve mathematical preconditions
  - distinguish textbook RSA from secure encodings
  - distinguish verification from identity trust
  - never treat examples as production key-generation guidance
  - cite source provenance and verification status
outputs: [definitions, typed_relations, correctness_checks, safety_constraints]

END FLOW