nedeľa 31. augusta 2025

Pavel Baráček-Jacquier – Diplomat, Cryptologist, and the Breaking of an Unbreakable Cipher Machine

 

Welcome to my blog dedicated to forgotten heroes of history! Today, we dive into the fascinating story of Pavel Baráček-Jacquier, a key figure in Czechoslovak diplomacy and cryptography, whose life was full of secrets, resistance, and brilliant inventions. His breaking of a cipher machine with an unbelievable 15 quadrillion combinations in 1935 was not just a technical triumph, but also a symbol of the fight against German espionage in the interwar period. This story is worth discovering.

Who Was Pavel Baráček-Jacquier?

Pavel Baráček-Jacquier (born 1885, died 1969) was a man of many talents – a Czechoslovak diplomat, inventor, cryptologist, and a key figure in the Czechoslovak resistance during World War I. Born in Prague into a family with French roots (hence the double surname), he studied law and engineering in Paris and Prague. His career began in the Austro-Hungarian administration, but after the outbreak of war in 1914, he joined the illegal resistance for Czechoslovak independence.

In Switzerland, where he lived in exile (1916–1918), he collaborated with Tomáš Garrigue Masaryk and Edvard Beneš. This is where his cryptographic career began – he organized secret communications for the resistance, facing the risk of interception by Austro-Hungarian censorship. According to historical sources, he also collaborated with Vsevolod Svatkovsky, director of the Russian State Telegraph Agency and an alleged agent of the Russian secret service Ochrana (Okhrana), which gave him access to Russian cipher techniques. The Ochrana, the Tsarist security police (1880–1917), was known for sophisticated surveillance and cipher methods, inspiring Baráček's inventions.

After the establishment of Czechoslovakia (1918), Baráček became a diplomatic representative in the Netherlands, Greece, and Switzerland, where he continued his cryptographic work. He was the founder of the Czechoslovak diplomatic cipher service and inventor of machines like the Kryptograf (1916–1918) and Condenser PBJ (1922–1924). The Kryptograf was a prototype based on the Vigenère cipher with an autokey and a scrambled Czech alphabet (31 letters), with a paper version using the St. Cyr cipher slide. The Condenser PBJ, Czechoslovakia's first rotor cipher machine, had an estimated 141 trillion combinations and served the diplomatic service until 1934.

Baráček was a man of serious character, determined to fight for freedom – his collaboration with the Ochrana provided inspiration but also risk, as the Ochrana was known for provocations and infiltration. After World War II, he lectured on cryptography, emphasizing the need for mathematics and lawyers in the field.

The Discovery: Breaking the Unbreakable Machine in 1935

In March 1935, Baráček lectured in Prague on "The Development and Current State of Ciphering." In the article in Prager Presse (March 21, 1935), he described how he broke a "known foreign machine" with "15 quadrillion combinations" in 10 days without knowing the key or the machine. This machine was considered absolutely secure, but Baráček deciphered it using cryptographic methods (likely frequency analysis and periodicity).

From the discussion, the most likely candidate is the Enigma (German machine), with around 1.05 × 10^16 combinations. The Enigma was available in Europe from 1923 and presented in Prague in 1924. Baráček's success was consistent with the Enigma's breaking by Poles in 1932, using weaknesses like operator errors and the reflector. Other candidates, like Sidney Hole's pneumatic machine (adapted by Štolba in Czechoslovakia) or M-138-A (American), had high combinations but lower prevalence in Czechoslovakia in 1935.

This discovery was groundbreaking – in an era of rising German tension, it showed that even "unbreakable" systems have flaws and contributed to the development of cryptography in Czechoslovakia.

Baráček's Influence on Cryptography

Baráček's inventions, like the Kryptograf (with the St. Cyr slide and autokey) and Condenser PBJ, were pioneering in Czechoslovak cryptography. The Kryptograf used a long key (15–20 letters) and message segmentation into sections, increasing security (estimated 10^14–10^29 combinations). His collaboration with the Ochrana gave him inspiration from Russian ciphers, which influenced these systems. After the war, he lectured on the need for cryptography in state security, influencing development in Czechoslovakia.

Baráček's Legacy

Baráček-Jacquier died in 1969, but his story remains inspirational. He was a symbol of how an individual can influence national security through intelligence and innovation. In today's era of cyber threats, he reminds us that cryptography is a key to freedom.

What do you think? Was the Enigma the machine, or a forgotten prototype like Hole's? Comment below!

streda 9. júla 2025

Lúštenie RSA pomocou "kvantového" počítania ála Čína? Nie je problém...

Kedysi dávno, ešte v r. 2001 som použil veľmi starú, ale elegantnú metódu na riešenie faktorizácie modulu RSA...Fermatova faktorizácia

Úloha bola rozlúštiť správu zašifrovanú pomocou RSA - ktorá bola ale kódovaná ala známa "kódová kniha", tj. veľmi ľahko lúštiteľná pomocou ceruzky a papiera - Kľúč na šifrovanie bol veľmi jednoduchý: (modul, e) = (2479, 101):

"...Kedze modul je maly, da sa pouzit metoda faktorizacie. 

Z faktorizacnych metod som si ako najjednoduchsiu a najrychlejsiu pre moje ucely zvolil klasicku Fermatovu metodu: 

Najprv som si vypocital hornu celociselnu hranicu z hodnoty odmocniny z modulu n=2479, t.j. h=[2479^(1/2)]=50. 

V prvom kroku som postupoval podla Fermatovej procedury, ktora je udana nasledovnou podmienkou (symbolika je ako obvykle, druha odmocnina je SQRT a mocnina je ozn. "strieskou" , t.j. '^'.): SQRT(h^2-n) by malo byt cele cislo. Ak nie je, hodnota h sa inkrementuje, t.j. h=h+1 a vypocet vyrazu opakujeme dotial, pokial nedostaneme cele cislo. Ak sme dospeli k celociselnemu vysledku a ked ozn. tuto hodnotu pism. a a cislo kroku v procedure ako k, dostavame rovnicu: sqrt((h+(k-1))^2-n)=a.


Z nej upravou ziskame nasledovnu rovnicu pre n: n=(h+(k-1)-a)*(h+(k-1)+a).

Co je vlastne n rozlozene na faktory p a q, t.j. n=p*q. 

Na nasom konkretnom module to vyzera nasaledovne:

I. sqrt(50^2-2479) = 4,582575694956, co nie je cele cislo, 

II. sqrt(51^2-2479) = 11,04536101719, co tiez nevyhovuje, 

III. sqrt(52^2-2479) = 15, dostali sme cele cislo, takze mozme upravovat: n = 2479 = (52+15)*(52-15)=67*37, p=67 a q=37.

Teraz je uz mozne pristupit k vypoctu desifrovacieho exponentu. 

Eulerova funkcia pre modul je fi(n) = fi(p)*fi(q) (co, mimochodom vyplyva z multiplikativnej vlastnosti tejto funkcie) = (p-1)*(q-1). 

Pre nase ciselne hodnoty je to: fi(2479)=(67-1)*(37-1) =2376. 

Z podmienky RSA pre sifrovaci a desifrovaci exponent e*d = 1 mod fi(n) vyplyva kongruencia 101*d = 1 mod 2376, ktora sa riesi Euklidovym algoritmom nasledovne: 

Rozpiseme si ju podla definicie: 101*d-1=2376*k, kde k je lubovolne cele cislo, z coho upravou 1=101*d+2376*k. 

Je to vlastne diofanticka rovnica. 

Takze teraz uz postupujeme podla algoritmu. 2376 = 101*23+53, 101=53*1+48, 53=48*1+5, 48=5*9+3, 5=3*1+2, 3=2*1+1 

Dostali sme zvysok 1, takze dalej postupujeme tak, ze si z posledne rovnosti vyjadrime tento zvysok a postupujeme naspat dosadzovanim jednotlivych medzivysledkov takto: 1=3+2*(-1)=3*2+5*(-1)=48*2+5*(-19)=53*(-19)+48*21=101*21+53*(-40)=2376*(- 40)+101*941 

Z tohto a z diofantickej rovnice vyplyva k=-40 a to co sme si zelali, nas desifrovaci exponent d=941...."

....


U našich východných výskumníkov bol tento modul o dosť väčší a predstavte si, mal dokonca "úctyhodných" 2831 bitov:


n = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999919

Všimnime si však, že je v ňom 542 deviatok, po ktorých nasledujú číslice 1 a 9, čo je celkovo 544 číslic. Je to síce prekvapujúce, ale aj toto číslo sa dá faktorizovať podľa "starého dobrého"  Fermata.

_________________________________________________________________________________

Nie je ťažké si uvedomiť, že dané číslo je veľmi blízko číslu 100^272 (pretože 272 * 2 = 544 číslic). Číslo 100 sa dá vyjadriť ako 10^2, dá sa z toho vypozorovať, že druhá odmocnina daného modulu musí  byť rádovo porovnateľná  s hodnotou 10^272. Takže nech

t = 10²⁷²

Pretože t² je približne rovné n, počítajme rozdiel:

rt² - n = 81

Určite viete, že druhá odmocnina z uvedeného výsledku je deväť, tj. √81 = 9, z toho jasne dostávame, že r = 9².

Ak si všetko čo sme doteraz zistili, zapíšeme do jedného riadku, dostávame:

n = t²-9²

Vieme, že z dobre známej identity a²-b² = (a+b)·(a-b) môžeme nahliadnuť, že:

n = (t+9)·(t-9). A sme na konci, tu je naša faktorizácia, tj. rozloženie na prvočinitele. Teda máme:

n = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009 · 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999991

Na záver, práve sme "zázračne" rozlomili 2831 bitový RSA modul s pomocou“quantového počítania”, a to takmer zadarmo. Z tohto malého exkurzu do elementárnej teórie čísel vyplýva varovanie:

Ak chcete šifrovať pomocou RSA, nikdy nepoužívajte čísla, ktoré majú unikátne a špecifické vlastnosti.

______________________________________________________________

Voľná inšpirácia výskumným článkom čínských odborníkov na quantové počítanie: A First Successful Factorization of RSA-2048 Integer by D-Wave Quantum Computer :)