#!/usr/bin/env python3 """Offline teaching arithmetic, not a constant-time signing service. All embedded private values are PUBLIC test fixtures. Never use them as keys. SEC1 v2; RFC6979 + verified EID3812; PureEd25519 RFC8032 cofactored verify; RFC8017 PSS, SHA256/MGF1-SHA256 with explicit salt-length policy. Checks use exceptions and remain active under python -O. Standard library only. """ from dataclasses import dataclass from hashlib import sha256, sha512 import hmac import json from math import gcd, lcm def require(ok, note): if not ok: raise ValueError(note) def check(ok, note): if not ok: raise RuntimeError(note) def bits2int(data, q): require(q > 1 and isinstance(data, bytes), 'bits2int input') return int.from_bytes(data, 'big') >> max(0, 8 * len(data) - q.bit_length()) def int2octets(x, q): require(0 <= x < q, 'scalar outside canonical interval') return x.to_bytes((q.bit_length() + 7) // 8, 'big') def bits2octets(digest, q): return int2octets(bits2int(digest, q) % q, q) def nonce6979(q, secret, digest, events=None): """Infinite candidate iterator. Resuming after yield means rejecting that k. Both r=0 and s=0 consumers resume the SAME iterator (EID3812). events, if supplied, stores each candidate and whether 1<=k= 3 and q % 2 == 1 and 1 <= secret < q, 'nonce parameters') require(isinstance(digest, bytes), 'digest must be bytes') V, K = b'\x01' * 32, b'\x00' * 32 def mac(k, msg): return hmac.new(k, msg, sha256).digest() seed = int2octets(secret, q) + bits2octets(digest, q) K = mac(K, V + b'\x00' + seed); V = mac(K, V) K = mac(K, V + b'\x01' + seed); V = mac(K, V) while True: parts = [] for _ in range((q.bit_length() + 255) // 256): V = mac(K, V); parts.append(V) k = bits2int(b''.join(parts), q) if events is not None: events.append({'candidate': k, 'in_range': 1 <= k < q, 'K': K.hex(), 'V': V.hex()}) if 1 <= k < q: yield k K = mac(K, V + b'\x00'); V = mac(K, V) @dataclass(frozen=True) class Curve: p: int a: int b: int G: tuple q: int def point(self, P): return P is not None and isinstance(P, tuple) and len(P) == 2 and all(type(x) is int and 0 <= x < self.p for x in P) and (P[1]**2 - P[0]**3 - self.a*P[0] - self.b) % self.p == 0 def add(self, P, Q): if P is None: return Q if Q is None: return P x, y = P; u, v = Q; p = self.p if x == u and (y + v) % p == 0: return None slope = ((3*x*x+self.a)*pow(2*y, -1, p) if P == Q else (v-y)*pow(u-x, -1, p)) % p z = (slope*slope-x-u) % p return z, (slope*(x-z)-y) % p def mul(self, n, P): require(type(n) is int and n >= 0, 'nonnegative scalar required') out = None while n: if n & 1: out = self.add(out, P) P = self.add(P, P); n >>= 1 return out def public(self, Q): return self.point(Q) and self.mul(self.q, Q) is None TOY = Curve(17, 2, 2, (5, 1), 19) P256 = Curve(int('ffffffff00000001000000000000000000000000ffffffffffffffffffffffff', 16), -3, int('5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b', 16), (int('6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296', 16), int('4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5', 16)), int('ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551', 16)) def ecdsa_candidate(C, d, z, k): """Domain parameters trusted; return None for a mathematically unsuitable k.""" require(1 <= d < C.q and type(z) is int, 'ECDSA scalar input') if not 1 <= k < C.q: return None R = C.mul(k, C.G) r = R[0] % C.q if r == 0: return None s = pow(k, -1, C.q) * (z + r*d) % C.q return (r, s) if s else None def ecdsa_verify(C, Q, z, sig): if not C.public(Q) or not isinstance(sig, tuple) or len(sig) != 2: return False r, s = sig if not all(type(t) is int and 1 <= t < C.q for t in (r, s)): return False w = pow(s, -1, C.q) R = C.add(C.mul(z*w % C.q, C.G), C.mul(r*w % C.q, Q)) return R is not None and R[0] % C.q == r def ecdsa_deterministic(C, d, msg, limit=1000): digest = sha256(msg).digest(); z = bits2int(digest, C.q) history, events = [], [] gen = nonce6979(C.q, d, digest, events) for _ in range(limit): k = next(gen); sig = ecdsa_candidate(C, d, z, k) history.append({'k': k, 'signature': sig}) if sig is not None: return sig, history, events raise ValueError('teaching attempt limit, not a proof of impossibility') # PureEd25519, extended Edwards coordinates (X,Y,Z,T), x=X/Z,y=Y/Z. EP = 2**255 - 19 EL = 2**252 + 27742317777372353535851937790883648493 ED = -121665 * pow(121666, -1, EP) % EP EI = (0, 1, 1, 0) def eadd(P, Q): X, Y, Z, T = P; U, V, W, S = Q a = (Y-X)*(V-U) % EP; b = (Y+X)*(V+U) % EP c = 2*ED*T*S % EP; d = 2*Z*W % EP e, f, g, h = (b-a) % EP, (d-c) % EP, (d+c) % EP, (b+a) % EP return e*f % EP, g*h % EP, f*g % EP, e*h % EP def emul(n, P): require(type(n) is int and n >= 0, 'nonnegative scalar') out = EI while n: if n & 1: out = eadd(out, P) P = eadd(P, P); n >>= 1 return out def eequal(P, Q): return (P[0]*Q[2]-Q[0]*P[2]) % EP == 0 and (P[1]*Q[2]-Q[1]*P[2]) % EP == 0 def eencode(P): inv = pow(P[2], -1, EP); x, y = P[0]*inv % EP, P[1]*inv % EP return (y | ((x & 1) << 255)).to_bytes(32, 'little') def edecode(data): require(isinstance(data, bytes) and len(data) == 32, 'point length') v = int.from_bytes(data, 'little'); sign, y = v >> 255, v & (2**255-1) require(y < EP, 'noncanonical y') x2 = (y*y-1) * pow(ED*y*y+1, -1, EP) % EP x = pow(x2, (EP+3)//8, EP) if x*x % EP != x2: x = x * pow(2, (EP-1)//4, EP) % EP require(x*x % EP == x2, 'point has no square root') require(x != 0 or sign == 0, 'zero x cannot have sign bit one') if x & 1 != sign: x = EP-x return x, y, 1, x*y % EP EB = edecode(bytes.fromhex('5866666666666666666666666666666666666666666666666666666666666666')) def edexpand(seed): require(isinstance(seed, bytes) and len(seed) == 32, 'seed length') h = sha512(seed).digest(); low = bytearray(h[:32]) low[0] &= 248; low[31] = (low[31] & 63) | 64 return int.from_bytes(low, 'little'), h[32:] def edsign(seed, msg): require(isinstance(msg, bytes), 'message bytes') a, prefix = edexpand(seed); A = eencode(emul(a, EB)) r = int.from_bytes(sha512(prefix+msg).digest(), 'little') % EL R = eencode(emul(r, EB)) k = int.from_bytes(sha512(R+A+msg).digest(), 'little') % EL S = (r+k*a) % EL return A, R + S.to_bytes(32, 'little') def edverify(A, msg, signature, cofactored=True, strict_key=False): """Default exactly the selected RFC8032 cofactored equation + canonical decoding. strict_key adds a LOCAL public-key admission policy, not an RFC requirement. Full hash scalar k is retained: mod-L reduction needn't preserve arbitrary torsion in the uncofactored comparison. """ if not isinstance(signature, bytes) or len(signature) != 64 or not isinstance(msg, bytes): return False try: P, R = edecode(A), edecode(signature[:32]) except (ValueError, TypeError): return False S = int.from_bytes(signature[32:], 'little') if S >= EL: return False if strict_key and (eequal(P, EI) or not eequal(emul(EL, P), EI)): return False k = int.from_bytes(sha512(signature[:32]+A+msg).digest(), 'little') left, right = emul(S, EB), eadd(R, emul(k, P)) if cofactored: left, right = emul(8, left), emul(8, right) return eequal(left, right) def enc_fields(*fields): require(len(fields) < 65536 and all(isinstance(x, bytes) and len(x) <= 65535 for x in fields), 'teaching field limit') return len(fields).to_bytes(2, 'big') + b''.join(len(x).to_bytes(4, 'big')+x for x in fields) def mgf1(seed, length): require(isinstance(seed, bytes) and type(length) is int and 0 <= length <= 2**32*32, 'MGF1 length') # Bytearray avoids quadratic repeated immutable concatenation. out = bytearray() for i in range((length+31)//32): out.extend(sha256(seed+i.to_bytes(4, 'big')).digest()) return bytes(out[:length]) def hash_to_unit(n, e, msg, domain=b'Theoryroad/RSA-FDH/v1', limit=100000): """Concrete teaching expansion, NOT a proof that SHA256 is a random oracle.""" require(type(n) is int and n >= 3 and type(e) is int and e >= 1, 'RSA public input') nb = (n.bit_length()+7)//8 label = enc_fields(domain, n.to_bytes(nb, 'big'), e.to_bytes(max(1,(e.bit_length()+7)//8), 'big'), msg) seed = sha256(label).digest() for counter in range(min(limit, 2**32)): raw = bytearray(mgf1(seed+counter.to_bytes(4,'big'), nb)) raw[0] &= 255 >> (8*nb-n.bit_length()) x = int.from_bytes(raw, 'big') if 0 < x < n and gcd(x, n) == 1: return x, counter+1 raise ValueError('hash-to-unit teaching budget exhausted') def fdh_sign(n, e, d, msg): y, attempts = hash_to_unit(n,e,msg) return pow(y,d,n), y, attempts def fdh_verify(n, e, msg, sig): if type(sig) is not int or not 0 < sig < n or gcd(sig,n) != 1: return False return pow(sig,e,n) == hash_to_unit(n,e,msg)[0] class FDHSimulator: """Executable trace of the elementary classical ROM reduction. roots supplies uniform independent units in the MATHEMATICAL model. Tests deliberately use exhaustive/specified finite roots, not secure randomness. target counts all first-seen messages, including sign requests and final lookup. """ def __init__(self, n, e, challenge, target, roots): require(0 < challenge < n and gcd(challenge,n) == 1 and target >= 1, 'simulator inputs') self.n, self.e, self.challenge, self.target = n,e,challenge,target self.roots = iter(roots); self.table = {}; self.signed = set(); self.events = [] def query(self, msg): if msg not in self.table: index = len(self.table)+1 if index == self.target: value, root = self.challenge, None else: root = next(self.roots) require(0 < root < self.n and gcd(root,self.n) == 1, 'root must be a unit') value = pow(root,self.e,self.n) self.table[msg] = (index,value,root) self.events.append({'message':msg.hex(),'index':index,'target':index==self.target,'value':value,'known_root':root}) return self.table[msg][1] def sign(self, msg): self.query(msg); root = self.table[msg][2] if root is None: raise ValueError('ABORT: challenged message requested for signing') self.signed.add(msg) return root def finish(self, msg, sig): value = self.query(msg) # Counts a previously unqueried final forgery. valid = type(sig) is int and 0 < sig < self.n and gcd(sig,self.n)==1 and pow(sig,self.e,self.n)==value if valid and msg not in self.signed and self.table[msg][0] == self.target: return sig return None def pss_encode(msg, em_bits, salt): require(isinstance(msg, bytes) and isinstance(salt, bytes) and type(em_bits) is int and em_bits >= 1, 'PSS encode input') require(len(msg) < 2**61, 'SHA256 message bit-length limit') em_len = (em_bits+7)//8 require(em_len >= 32+len(salt)+2, 'encoding too short') H = sha256(b'\x00'*8+sha256(msg).digest()+salt).digest() DB = b'\x00'*(em_len-len(salt)-34)+b'\x01'+salt masked = bytearray(x^y for x,y in zip(DB,mgf1(H,len(DB)))) masked[0] &= 255 >> (8*em_len-em_bits) return bytes(masked)+H+b'\xbc' def pss_verify_em(msg, em, em_bits, salt_len=32): if not isinstance(msg, bytes) or not isinstance(em, bytes) or type(em_bits) is not int or em_bits < 1 or type(salt_len) is not int or salt_len < 0: return False em_len=(em_bits+7)//8 if len(msg) >= 2**61 or len(em) != em_len or em_len < 32+salt_len+2 or em[-1] != 188: return False masked,H = em[:-33],em[-33:-1]; mask = 255 >> (8*em_len-em_bits) if masked[0] & (255^mask): return False DB=bytearray(x^y for x,y in zip(masked,mgf1(H,len(masked)))); DB[0] &= mask ps_len=em_len-salt_len-34 if DB[:ps_len] != b'\x00'*ps_len or DB[ps_len] != 1: return False salt = bytes(DB[-salt_len:]) if salt_len else b'' expected=sha256(b'\x00'*8+sha256(msg).digest()+salt).digest() return hmac.compare_digest(H,expected) def pss_sign(n,d,msg,salt): require(n >= 3 and d >= 1, 'RSA parameters') EM=pss_encode(msg,n.bit_length()-1,salt) return pow(int.from_bytes(EM,'big'),d,n).to_bytes((n.bit_length()+7)//8,'big') def pss_verify(n,e,msg,sig,salt_len=32): if type(n) is not int or n < 3 or type(e) is not int or e < 1 or not isinstance(sig,bytes): return False k=(n.bit_length()+7)//8; em_len=(n.bit_length()+6)//8 if len(sig) != k: return False s=int.from_bytes(sig,'big') if s >= n: return False m=pow(s,e,n) if m >= 1 << (8*em_len): return False return pss_verify_em(msg,m.to_bytes(em_len,'big'),n.bit_length()-1,salt_len) # PUBLIC RSA Laboratories examples 1 and 2, retained by the Go project. # Numbers only; our PSS profile uses SHA256, unlike the original SHA1 vectors. RSA_FIXTURES = [ { 'n': int('a56e4a0e701017589a5187dc7ea841d156f2ec0e36ad52a44dfeb1e61f7ad991d8c51056ffedb162b4c0f283a12a88a394dff526ab7291cbb307ceabfce0b1dfd5cd9508096d5b2b8b6df5d671ef6377c0921cb23c270a70e2598e6ff89d19f105acc2d3f0cb35f29280e1386b6f64c4ef22e1e1f20d0ce8cffb2249bd9a2137', 16), 'e': int('010001', 16), 'd': int('33a5042a90b27d4f5451ca9bbbd0b44771a101af884340aef9885f2a4bbe92e894a724ac3c568c8f97853ad07c0266c8c6a3ca0929f1e8f11231884429fc4d9ae55fee896a10ce707c3ed7e734e44727a39574501a532683109c2abacaba283c31b4bd2f53c3ee37e352cee34f9e503bd80c0622ad79c6dcee883547c6a3b325', 16), 'p': int('e7e8942720a877517273a356053ea2a1bc0c94aa72d55c6e86296b2dfc967948c0a72cbccca7eacb35706e09a1df55a1535bd9b3cc34160b3b6dcd3eda8e6443', 16), 'q': int('b69dca1cf7d4d7ec81e75b90fcca874abcde123fd2700180aa90479b6e48de8d67ed24f9f19d85ba275874f542cd20dc723e6963364a1f9425452b269a6799fd', 16), }, { 'n': int('01d40c1bcf97a68ae7cdbd8a7bf3e34fa19dcca4ef75a47454375f94514d88fed006fb829f8419ff87d6315da68a1ff3a0938e9abb3464011c303ad99199cf0c7c7a8b477dce829e8844f625b115e5e9c4a59cf8f8113b6834336a2fd2689b472cbb5e5cabe674350c59b6c17e176874fb42f8fc3d176a017edc61fd326c4b33c9', 16), 'e': int('010001', 16), 'd': int('027d147e4673057377fd1ea201565772176a7dc38358d376045685a2e787c23c15576bc16b9f444402d6bfc5d98a3e88ea13ef67c353eca0c0ddba9255bd7b8bb50a644afdfd1dd51695b252d22e7318d1b6687a1c10ff75545f3db0fe602d5f2b7f294e3601eab7b9d1cecd767f64692e3e536ca2846cb0c2dd486a39fa75b1', 16), 'p': int('016601e926a0f8c9e26ecab769ea65a5e7c52cc9e080ef519457c644da6891c5a104d3ea7955929a22e7c68a7af9fcad777c3ccc2b9e3d3650bce404399b7e59d1', 16), 'q': int('014eafa1d4d0184da7e31f877d1281ddda625664869e8379e67ad3b75eae74a580e9827abd6eb7a002cb5411f5266797768fb8e95ae40e3e8a01f35ff89e56c079', 16), }, ] ED_VECTORS = [ ('9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60', '', 'd75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a', 'e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b'), ('4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb','72', '3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c', '92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00'), ('c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7','af82', 'fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025', '6291d657deec24024827e69c3abe01a30ce548a284743a445e3680d7db5ac3ac18ff9b538d16f290ae67f760984dc6594a7c15e9716ed28dc027beceea1ec40a')] def main(): result = {} check(TOY.public(TOY.G) and P256.public(P256.G), 'domain generators') finite=good=zero=0 for d in range(1,19): Q=TOY.mul(d,TOY.G) for z in range(19): for k in range(1,19): finite+=1;sig=ecdsa_candidate(TOY,d,z,k) if sig is None: zero+=1 else: good+=1 check(ecdsa_verify(TOY,Q,z,sig),'ECDSA correctness') check(ecdsa_verify(TOY,Q,z,(sig[0],19-sig[1])),'ECDSA sign flip') d,z1,z2,k = 7,4,9,3 sig1,sig2=ecdsa_candidate(TOY,d,z1,k),ecdsa_candidate(TOY,d,z2,k) r,s1=sig1; _,s2=sig2 recovered_k=(z1-z2)*pow(s1-s2,-1,19)%19 recovered_d=(s1*recovered_k-z1)*pow(r,-1,19)%19 check((recovered_k,recovered_d)==(k,d),'nonce recovery') mirror=ecdsa_candidate(TOY,d,z2,19-k) wrong_k=(z1-z2)*pow(s1-mirror[1],-1,19)%19 wrong_d=(s1*wrong_k-z1)*pow(r,-1,19)%19 right_k=(z1-z2)*pow(s1+mirror[1],-1,19)%19 check(right_k==k and TOY.mul(wrong_d,TOY.G)!=TOY.mul(d,TOY.G),'opposite nonce structural migration') result['opposite_nonce']={'second_signature':mirror,'same_nonce_formula':[wrong_k,wrong_d],'opposite_nonce_formula_k':right_k,'wrong_public':TOY.mul(wrong_d,TOY.G)} result['ecdsa_toy']={'p':17,'q':19,'G':TOY.G,'Q':TOY.mul(d,TOY.G),'nonce_point':TOY.mul(k,TOY.G),'z':[z1,z2],'signatures':[sig1,sig2],'recovered':[recovered_k,recovered_d],'all_candidates':finite,'accepted':good,'retry':zero} secret=int('C9AFA9D845BA75166B5C215767B1D6934E50C3DB36E89B127B8A622B120F6721',16) vectors=[(b'sample','A6E3C57DD01ABE90086538398355DD4C3B17AA873382B0F24D6129493D8AAD60','EFD48B2AACB6A8FD1140DD9CD45E81D69D2C877B56AAF991C34D0EA84EAF3716','F7CB1C942D657C41D436C7A1B6E29F65F3E900DBB9AFF4064DC4AB2F843ACDA8'), (b'test','D16B6AE827F17175E040871A1C7EC3500192C4C92677336EC2537ACAEE0008E0','F1ABB023518351CD71D881567B1EA663ED3EFCF6C5132B354F28D3B0B7D38367','019F4113742A2B14BD25926B49C649155F267E60D3814B4C0CC84250E46F0083')] out=[] for msg,kn,rn,sn in vectors: sig,hist,events=ecdsa_deterministic(P256,secret,msg) check(hist[0]['k']==int(kn,16) and sig==(int(rn,16),int(sn,16)),'RFC6979 P256 vector') check(ecdsa_verify(P256,P256.mul(secret,P256.G),bits2int(sha256(msg).digest(),P256.q),sig),'P256 verify') out.append({'message':msg.decode(),'k':kn.lower(),'r':rn.lower(),'s':sn.lower()}) toy_retry=None for i in range(100): msg=b'retry/'+str(i).encode();sig,hist,events=ecdsa_deterministic(TOY,7,msg) if len(hist)>1: toy_retry={'message':msg.decode(),'digest':sha256(msg).hexdigest(),'z':bits2int(sha256(msg).digest(),19),'history':hist,'candidates':events};break check(toy_retry is not None,'find zero-component retry') result['rfc6979']={'vectors':out,'nonbyte_example':{'q':19,'input':'ff','bits2int':bits2int(b'\xff',19),'bits2octets':bits2octets(b'\xff',19).hex(),'int2octets18':int2octets(18,19).hex(),'roundtrip18':bits2int(int2octets(18,19),19)},'zero_component_retry':toy_retry} ed_out=[] for seed,msg,public,sig in ED_VECTORS: seed,msg,public,sig=map(bytes.fromhex,(seed,msg,public,sig)) A,S=edsign(seed,msg) check((A,S)==(public,sig),'RFC8032 signing vector') check(edverify(A,msg,S) and edverify(A,msg,S,False,True),'Ed25519 both equations') check(not edverify(A,msg+b'x',S),'Ed25519 changed message') check(not edverify(A,msg,S[:32]+(int.from_bytes(S[32:],'little')+EL).to_bytes(32,'little')),'noncanonical S') for bad in (S[:-1],S+b'\0'):check(not edverify(A,msg,bad),'bad length') ed_out.append({'message':msg.hex(),'public':A.hex(),'signature':S.hex()}) identity=eencode(EI); order2=eencode((0,EP-1,1,0)); zero=b'\0'*32 arbitrary=b'public fixture only' boundaries={'identity_key_identity_R':edverify(identity,arbitrary,identity+zero), 'identity_key_order2_R_cofactored':edverify(identity,arbitrary,order2+zero), 'identity_key_order2_R_uncofactored':edverify(identity,arbitrary,order2+zero,False), 'strict_key_rejects_identity':not edverify(identity,arbitrary,identity+zero,True,True)} check(list(boundaries.values())==[True,True,False,True],'cofactor/key-policy distinction') for bad in [EP.to_bytes(32,'little'),((1<<255)|1).to_bytes(32,'little')]: try:edecode(bad) except ValueError:pass else:raise RuntimeError('bad point accepted') seed=bytes.fromhex(ED_VECTORS[0][0]);a,_=edexpand(seed);A=eencode(emul(a,EB));msg=b'known secret for edge fixture';r=7 R=eencode(eadd(emul(r,EB),(0,EP-1,1,0)));challenge=int.from_bytes(sha512(R+A+msg).digest(),'little') S=(r+challenge*a)%EL;sig=R+S.to_bytes(32,'little') mixed={'cofactored':edverify(A,msg,sig),'uncofactored':edverify(A,msg,sig,False),'strict_public_key_only':edverify(A,msg,sig,True,True)} check(mixed=={'cofactored':True,'uncofactored':False,'strict_public_key_only':True},'mixed-order R with honest public key') matrix=[ [edverify(identity,arbitrary,identity+zero),edverify(identity,arbitrary,identity+zero,False),edverify(identity,arbitrary,identity+zero,True,True)], [edverify(identity,arbitrary,order2+zero),edverify(identity,arbitrary,order2+zero,False),edverify(identity,arbitrary,order2+zero,True,True)], list(mixed.values())] check(matrix==[[True,True,False],[True,False,False],[True,False,True]],'full validation matrix') result['ed25519']={'validation_matrix':matrix,'mixed_R_known_secret_fixture':mixed,'vectors':ed_out,'boundaries':boundaries,'identity':identity.hex(),'order2':order2.hex()} # Full-domain hash on the explicitly insecure N=11*13 fixture. n,e,d=143,7,43; msg=enc_fields(b'Theoryroad/lesson/v1',b'signature',b'allow=demo') sig,y,attempts=fdh_sign(n,e,d,msg) check(fdh_verify(n,e,msg,sig),'FDH concrete fixture') units=[x for x in range(1,n) if gcd(x,n)==1] check(len({pow(x,e,n) for x in units})==len(units)==120,'RSA units permutation') check(all(pow(pow(x,e,n),d,n)==x for x in units),'RSA inverse') challenge=pow(17,e,n); traces=[] # Two explicit hashes, one sign-first request, and an unseen final message. for target in range(1,5): sim=FDHSimulator(n,e,challenge,target,[2,3,5,7,8,9]) try: sim.query(b'a'); signed=sim.sign(b'b');sim.query(b'c') value=sim.query(b'd'); forgery=pow(value,d,n) # educational omniscient forger extracted=sim.finish(b'd',forgery) traces.append({'target':target,'abort':False,'extracted':extracted,'table':sim.events}) except ValueError: traces.append({'target':target,'abort':True,'extracted':None,'table':sim.events}) check(sum(t['extracted'] is not None for t in traces)==1,'guess-index coupling') unqueried=FDHSimulator(n,e,challenge,1,[]) check(unqueried.finish(b'unseen',17)==17,'final forced oracle lookup') check(fdh_verify(n,e,msg,sig+n) is False,'FDH canonical representative') result['fdh']={'message':msg.hex(),'n':n,'e':e,'d':d,'hash_unit':y,'signature':sig,'rejection_attempts':attempts,'units':len(units),'challenge':challenge,'guess_traces':traces,'unqueried_final':unqueried.events} salt=bytes(range(32)); m=b'Theoryroad offline PSS lesson'; rows=[]; mutation_count=0 for key in RSA_FIXTURES: n,e,d,p,q=(key[x] for x in ('n','e','d','p','q')) check(n==p*q and (e*d)%lcm(p-1,q-1)==1,'published RSA fixture consistency') S=pss_sign(n,d,m,salt);EM=pss_encode(m,n.bit_length()-1,salt) check(pss_verify(n,e,m,S),'PSS RSA wrapper') check(not pss_verify(n,e,m,S,20),'salt policy mismatch') check(not pss_verify(n,e,m+b'!',S),'message changed') check(not pss_verify(n,e,m,S[:-1]),'short signature') check(not pss_verify(n,e,m,n.to_bytes(len(S),'big')),'s equals modulus') # Every single EM bit flip is rejected, independent of RSA arithmetic. for j in range(len(EM)): for b in range(8): bad=bytearray(EM);bad[j]^=1<> (8*len(EM)-(n.bit_length()-1));DB[len(EM)-66]=2 bad=bytearray(x^y for x,y in zip(DB,mgf1(H,len(DB)))) bad[0] &= 255 >> (8*len(EM)-(n.bit_length()-1));bad=bytes(bad)+H+b'\xbc' badS=pow(int.from_bytes(bad,'big'),d,n).to_bytes(len(S),'big') check(not pss_verify(n,e,m,badS),'signed invalid delimiter') faults={} for label,pos,bit in [('trailer',len(EM)-1,1),('zero_PS',0,1),('salt',len(EM)-34,1),('digest',len(EM)-2,1)]: changed=bytearray(EM);changed[pos]^=bit faults[label]=not pss_verify_em(m,bytes(changed),n.bit_length()-1,32) if n.bit_length()==1024: changed=bytearray(EM);changed[0]|=128 faults['reserved_high_bit']=not pss_verify_em(m,bytes(changed),1023,32) check(all(faults.values()),'named PSS gates') rows.append({'named_corruptions_rejected':faults,'mod_bits':n.bit_length(),'k':len(S),'em_bits':n.bit_length()-1,'em_len':len(EM),'PS_bytes':len(EM)-66,'reserved_high_bits':8*len(EM)-(n.bit_length()-1),'salt':salt.hex(),'em':EM.hex(),'signature':S.hex(),'signed_bad_delimiter_rejected':True}) # Zero salt and minimum room for SHA256: 34-byte EM, 265 meaningful bits. min_em=pss_encode(b'',265,b'') check(pss_verify_em(b'',min_em,265,0),'zero-salt minimum') try:pss_encode(b'',264,b'') except ValueError:pass else:raise RuntimeError('short encoding accepted') key=RSA_FIXTURES[1];overflow_m=1<<1024 check(overflow_m