NONOCRYPT

Visual key verification using nonogram puzzles.

Turn any cryptographic public key into a picture. Verify keys by solving a puzzle.

  Alice's Key Fingerprint         Bob's Key Fingerprint
  ┌────────────────────┐          ┌────────────────────┐
  │██  ██    ████  ██  │          │██  ██    ████  ██  │
  │    ████████  ████  │          │    ████████  ████  │
  │██████    ██    ██  │          │██████    ██    ██  │
  │██  ██  ██████████  │          │██  ██  ██████████  │
  │    ██████  ██      │          │    ██████  ██      │
  └────────────────────┘          └────────────────────┘

  MATCH (100% identical) -- key verified!

The idea

Nonograms are picture logic puzzles where you fill cells based on row/column clues. Computing clues from an image is trivial, but solving clues back to an image is NP-complete (Ueda & Nagao, 1996).

NONOCRYPT uses this one-way property to create visual fingerprints for cryptographic keys:

1. Any public key (ML-KEM, RSA, Ed25519, etc.) is hashed into a binary image
2. The image's nonogram clues become a shareable puzzle
3. To verify a key, solve the puzzle and compare the revealed image
4. Same key always produces the same picture -- like Signal's safety numbers, but visual

The verification ceremony is interactive and engaging: you solve a puzzle, an image emerges, you compare. This makes key verification something people actually want to do.

Quick start

# Interactive demo
python3 demo.py

# C version
make && ./nonocrypt_demo "HELLO" "test message"

Python API

from nonocrypt import KeyFingerprint, compare_fingerprints

# Generate a visual fingerprint from any key bytes
fp = KeyFingerprint.from_bytes(public_key_bytes, grid_size=12)

# Display the image (your visual key identity)
print(fp.as_image())

# Share as a nonogram puzzle (clues only, no solution)
print(fp.as_puzzle())

# Compare two fingerprints
fp_alice = KeyFingerprint.from_bytes(alice_pk)
fp_bob   = KeyFingerprint.from_bytes(alice_pk)  # same key
print(fp_alice.matches(fp_bob))    # True
print(compare_fingerprints(fp_alice, fp_bob))  # visual side-by-side

# Detect tampering: even 1 bit change = completely different image
tampered = bytearray(alice_pk)
tampered[0] ^= 1
fp_evil = KeyFingerprint.from_bytes(bytes(tampered))
print(fp_alice.matches(fp_evil))   # False
print(fp_alice.similarity(fp_evil))  # ~50% (random chance)

# Interactive verification: solve the puzzle to see the image
solved_image = fp.verify_by_solving()

# Text-based key identities (pixel art)
fp = KeyFingerprint.from_text("ALICE")
print(fp.as_image())

Verification ceremony

  1. Alice computes her key fingerprint:      fp = KeyFingerprint.from_bytes(pk)
  2. Alice shows Bob the image (in person):   print(fp.as_image())
  3. Alice sends the puzzle (over network):   puzzle = fp.serialize()
  4. Bob receives and solves the puzzle:      solved = fp.verify_by_solving()
  5. Bob compares with what Alice showed:     matches = (solved == expected)
  6. If images match, the key is authentic!

Solving the puzzle is NP-hard, so it doubles as proof-of-work. The effort demonstrates the verifier engaged with the key material, not just skipped past a hex string comparison.

Additional features

Nonogram encryption (proof-of-work model)

NONOCRYPT can also encrypt messages where the sender must solve the recipient's puzzle:

from nonocrypt import keygen_from_text, encrypt, decrypt

pk, sk = keygen_from_text("HELLO")
ct, _, solve_time = encrypt(pk, b"secret message")  # NP-hard solving
plaintext = decrypt(sk, ct)                          # instant

This creates an unusual asymmetric cost model useful for anti-spam, rate limiting, and puzzle-based access control.

Nonogram hash

Hash arbitrary data into a visual nonogram puzzle:

from nonocrypt import nono_hash

row_clues, col_clues = nono_hash(b"data", grid_size=10)

Commitment scheme

Commit to an image without revealing it:

from nonocrypt import commit, open_commitment

commitment, randomness = commit(image)
assert open_commitment(image, randomness, commitment)

Architecture

nonocrypt/
├── nonogram.py        Core engine: clue computation, hybrid solver
├── nonocrypt.py        KeyFingerprint (primary), encryption (secondary)
├── visual.py           Text-to-pixel-art, ASCII rendering, animation
├── demo.py             Interactive demo (6 demonstrations)
├── benchmark.py        Performance benchmarks
├── analysis.py         Viability analysis
├── nonocrypt.h/.c      C implementation (standalone, zero dependencies)
├── demo_c.c            C demo
├── benchmark_c.c       C benchmarks
└── Makefile

Solver

The nonogram solver uses three optimizations:

1. Leftmost/rightmost overlap -- O(n*k) per line with enumeration fallback for remaining unknowns
2. Dirty-line tracking -- only re-solves rows/columns affected by changes
3. MRV heuristic -- backtracking picks the most constrained cell first

How it compares

Feature	NONOCRYPT	Signal Safety Numbers	SSH Key Art	PGP Fingerprints
Format	Picture (nonogram)	Numeric (60 digits)	ASCII art (randomart)	Hex (40 chars)
Interactive	Solve a puzzle	Compare numbers	Glance at art	Compare hex
Engagement	High (fun)	Low (tedious)	Medium	Low
Tamper detection	Visual difference	Digit difference	Art difference	Hex difference
Memorable	Yes (images)	No	Somewhat	No
Shareable	As puzzle	As text	As text	As text

Viability

Run python3 analysis.py for full empirical analysis.

As primary encryption: not viable (no average-case hardness proof, expensive encryption, unknown security level).

As visual verification layer: viable and compelling. Use alongside established post-quantum schemes (ML-KEM, ML-DSA). The nonogram puzzle gives users an engaging, memorable way to verify keys that's more intuitive than comparing hex strings.

Disclaimer

Research prototype. Not peer-reviewed. Use NIST-standardized schemes for production cryptography.