Mike Tate Mathematics

Tag: cryptanalysis

  • Al-Kindi Made Ciphers Confess

    Al-Kindi Made Ciphers Confess

    The first philosopher of the Arabs spent his career turning Greek science into Arabic — and in one short side work, he taught a scrambled alphabet to give itself up.

    Al-Kindi in ninth-century Baghdad, tallying the letter counts of a cipher manuscript

    Boethius carried the cargo into Latin in a prison cell, racing an executioner. But Greek learning in those centuries was moving in two directions at once, and the eastbound road led somewhere the westbound one never reached: a city not yet forty years old, rich beyond precedent, where the cargo would not merely be carried but cross-examined. Baghdad.

    The cross-examiner was Abu Yusuf Ya'qub ibn Ishaq al-Kindi — remembered by the title his own people gave him, the philosopher of the Arabs, the first of them. Aristotle's operator was SORT. Nicomachus's was SHAPE. Proclus's was COMMENT, Boethius's CARRY. Al-Kindi's is DECODE: take a thing built to hide its pattern, and find the pattern anyway — because the hiding place is never as structureless as it looks.

    I. The philosopher of the Arabs

    Al-Kindi was born in Kufa around 801, into the tribe of Kinda — old Arab aristocracy; his father had governed Kufa. He was educated in Basra, then in Baghdad, the Abbasid capital founded in 762, which in his lifetime grew into one of the largest cities on earth. Its caliphs were spending that scale on an unprecedented project: the systematic translation of Greek science into Arabic, the enterprise centered on Baghdad's House of Wisdom.

    Al-Kindi rose inside it. Under the caliph al-Ma'mun, and then under al-Mu’tasim — who made him tutor to his son Ahmad — he stood at the head of the translation generation, the Arab thinker to whom Greek philosophy would have to answer in a new language. His On First Philosophy, the founding work of philosophy in Arabic, is dedicated to al-Mu’tasim. The favor did not outlast the reign: under a later caliph, al-Mutawakkil, the biographers say he fell from grace, and his library — the famous Kindiana — was seized for a time. He died in Baghdad in 873.

    II. The great turning

    Understand what his circle actually did, because CARRY is too weak a word for it. They corrected and recast the translations as they made them; the Arabic Plotinus that issued from his orbit circulated as the Theology of Aristotle — Greek mysticism traveling under Aristotle's name, a trick this line has met before, in Proclus's margin. Al-Kindi's own rule, stated at the front of On First Philosophy, was that truth is not diminished by arriving from far away: we should not be ashamed to acknowledge it, he wrote, from whatever quarter it reaches us.

    Then look at the shelf. Ibn al-Nadim's Fihrist, the great tenth-century catalogue of Baghdad's books, lists more than 260 works under al-Kindi's name. Logic and metaphysics. Geometry and arithmetic. A treatise on the Indian numerals — the place-value counting then traveling west out of India, which his writing helped naturalize in Arabic. A book on optics that Latin Europe would read as De aspectibus, still teaching Roger Bacon four centuries after its author's death. Music theory, argued in ratios. Medicine. Tides, mirrors, the grading of drugs. And at the far, practical end of the shelf, a chemistry of perfume and a treatise on swords. Running through all of it is a conviction the rest of this line would recognize: number is not one subject among the others but the instrument that makes the others exact. He graded the strength of compound drugs by mathematical proportion, and set music's consonances out as ratios.

    Most of those 260 are lost. We know this man, to an uncomfortable degree, by his table of contents. Hold that proportion in mind — it is about to matter.

    III. The side work

    An empire run on paper runs on secrets: sealed orders, tax registers, couriers riding between Baghdad and the provinces. And the standard lock on a written secret was substitution — replace every letter of the message with another letter or symbol, the same swap throughout. To anyone without the key, the page is noise. Worse, it is provably stubborn noise: the alphabet can be scrambled in more ways than a lifetime of clerks could test one by one. For centuries, that was the end of the matter. The lock looked absolute because the search looked endless.

    Somewhere in his mountain of writing sits a short, workmanlike treatise: On Deciphering Cryptographic Messages, written around 850. It does not attack the cipher. It attacks the language underneath it.

    His method, in his own procedure: find a plaintext in the same language as the secret message, long enough to fill a sheet or so, and count the occurrences of each letter. Call the most frequent letter the first, the next most frequent the second, and so on down. Then take the encrypted message and count its symbols the same way — and match the two rankings.

    Run it on English and watch how little work it takes. Take a thousand letters of ordinary prose and tally them: e appears something like 170 times, t around 130, a around 90, and the counts fall away steeply from there. Now scramble the alphabet — any scramble you like — and encrypt the page. The result is unreadable, but the tally survives untouched: the commonest symbol still appears some 170 times, the next around 130, the next around 90. You do not yet know what any symbol means. You know exactly which one is e.

    That is all of it, and it is everything. A language does not spend its letters evenly. In English, e does more work than any other letter by a wide margin, with t, a, and o behind it; a few letters carry most of every page ever written, and a few barely appear at all. Arabic has its own such profile — and Arabic scholars had been counting their language's letters for generations, in grammar and in the close study of the Quran's text, so the tallies lay ready to hand. Substitution changes every symbol on the page. It cannot change the shape of the counts. The commonest symbol in the secret message is the commonest letter of the language, wearing a mask — and rank by rank, most frequent to rarest, the whole alphabet unscrambles itself.

    This is frequency analysis: the founding move of cryptanalysis, written down fully formed, as a side work, by a man whose day work was metaphysics. The cipher's strength was never randomness. It was the appearance of randomness — and counting is the refusal to be fooled by appearances.

    IV. The sleep

    Of the more than 260 works, a remnant survives — some in Latin dress, some in Arabic manuscripts. The deciphering treatise hung by a single thread: one copy, and then silence. Europe would not write the method down again for some six hundred years. When David Kahn published The Codebreakers in 1967 — the modern history of the entire subject — al-Kindi's treatise was still unknown to scholarship.

    Then, in 1987, scholars of the Arab Academy of Damascus published a cache of old Arabic cryptology manuscripts that had been found in Istanbul's Süleymaniye Library. The oldest of them was his.

    Do the arithmetic the way he would have wanted it done, by counting: written around 850, printed for the world in 1987. The founding text of codebreaking slept for 1,137 years — through the whole history of the art it founded, through every cipher bureau and black chamber that reinvented its method in ignorance of its name.

    V. Count, and it confesses

    Every operator in this line so far worked on things that showed their faces: a world to sort, a number to shape, a text to comment on, a cargo to carry. DECODE is the first operator for a world that hides — and its lesson reaches well past ciphers. Disguise is not formlessness. A scrambled message is not the absence of a pattern; it is a pattern whose frequencies survived the scrambling, waiting for someone patient enough to tally them.

    Al-Kindi spent a life arguing that truth should be taken from whatever quarter it arrives in. His smallest book makes the complementary point: truth also stays where it was left, in the counts, no matter what costume it is wearing.

    A message that looks like noise is a pattern whose counts you haven't taken yet.

    — Mike Tate, MikeTateMath