Programming Praxis

Let’s begin with the random number generation. Blum-Blum-Shub requires two large primes, each congruent to 3 (mod 4), and a seed coprime to the two primes; the random sequence squares the seed modulo the product of the two primes, keeping only the final bit:

(define *n*
  (let ((p 18446744073709551359)
    (q 18446744073709551427))
  (* p q)))

(define *s* 20150106)

(define (bbs)
  ((set! *s* (modulo (* *s* *s*) *n*))
  ((modulo *s* 2))

We used two 64-bit primes; in practice, those would likely be 512 bits or larger, and the seed would be of a similar size. Given the random bits, a random letter can be generated like this:

(define (rand-letter)
  (let loop ((i 26) (ds (list)))
    (if (positive? i)
        (loop (- i 1) (cons (bbs) ds))
        (let ((m (undigits ds 2)))
          (if (char
                (+ (modulo m 26) 65)))))))

The largest multiple of 26 less than 2^26 is 67108860. We can check that the random number generator works by looking at a histogram of the frequency counts of the output from rand-letter:

> (map cdr (uniq-c char=? (sort char<? (list-of (bbs) (x range 2600000)))))
(99962 100017 100553 100101 99494 99809 100031 100192 100004
 100176 99955 99378 100306 100148 100188 99734 100098 100181
 99890 100182 100035 100233 99802 100227 99276 100028)

Building a one-time pad is just a simple nest of three loops, for the rows, columns and letter-groups:

(define (one-time-pad rows cols)
  (for (r 0 rows)
    (for (c 0 cols)
      (for (j 0 5)
        (display (rand-letter)))
      (display #\space))
    (newline)))

And here is a one-time pad:

> (one-time-pad 50 10)
RJPFX OLNUW UFSXH XTKCL GEYMV VSSNU VHVSY ZUBUC XVKRY YHFEF
XYMSZ JRIFU RTIYH SUSQG APQDW VHRDC XIYRF XZFTJ UFRUF UIAKW
HIJQS HCIYP GUGOE FTZAG XZSVM DDRHV MGBOY CFSKX LHCCM LADMP
NRAJN QMZMX PKOBY FMAZO GDFQX CBPBO WQDCQ WDLYQ CWAHM NGQHC
KCNPI KKFBN KHJRR YEQCY ZBWDP FMTNJ FYEHX QIRPP YDLKJ ROMEK
ZOXVV PPFOI GWDGS FPJKZ AYIMB MLISK IKDTV IMWZE GZJUL CVNKF
YWNPM GWRHR YEQGY ZWCNT QNOEV ZYBHT ONPWL EJYSH XFRQO XYSLG
IRIXU MPKAO UJTXP RNJBU ATDDB LHCFB EQWZJ MTVMA DYVRM XBXYG
HAGQM BDXOW QSXBR UDJQD AGDJW QQGPJ YHFAI JUPMJ XKQJJ WVHBI
GSBNT FCTXW MTUBZ WGCXL TMIPA WUKMF RMZTM GYKPJ QOYZE MJTOL
MXXRI NDNBT KXTOI YQONE VUMPE DWMFX DQPYB IPTVW OJZGA JIRMU
HFTZZ HYSAD QPDIM EGVAY ADYPT NMEHD VRYCI GNZNV XWOTV OOLCS
KWWJN CYKPJ LKOVS DMAFL DMJXE JVTZB LSPFX LSWMU NYEDN WONTP
QETKW SULQA WEQWE PLEHN NZTVD MGJER KKKIM DITTV MDOUR QKYTB
QWVMJ IXUST DZUAV RCDDT JSXDY QHDSZ RFIDL BCVRJ UOEGZ JDESI
MDDMK TJQNW ZKZBY VOSHY YPGEH YEJWQ JHYWM QFNQR HNWYV QQVYY
PCKUT LQASO BKIYY MSCWN JKWDL EKGND CBQUM VKQGZ MEPOB HNRVF
OJHIN NWHRC RFIJU SDNHZ CHBFW INFEF VIAPM KFBQB YOVIF NQQNW
DSOQA CWMMO SXELL WSCLU RDVCJ YFUXN UBXJM AZSCS FYZIK MRTRN
BNAYM QYMZP TNUZB IWYZU IGTQA GUTUR LHNCN UUDCT XJBCS HIRXF
ZIZSQ BHGHF WOOUR IUVNI KYBVV LUTBR MHDHS BSYYU LQJDN RBHNN
KJLGU NGVES EFVEB KASJM DYTTV HLNSZ VYAZX RWPHQ DRMHA CTYKA
QUWPG HPJJX HWUEB GTQHV KPSXX YSHMM LOADK DYDOY WIALH GFGJL
SUETF STDOJ ADKCL HTLJR GBBGW ZLLQS TVDQW FGTHP EJASO ZCRMR
TUEST GKDHR UBHVX BXGJD MBCDH XUBWT WTTNG SVEDJ JWXTV XCUPD
DHVTE MOIGQ PDYZR FEUOZ OGIPU RXKBA UKDKH RQULZ KKVKH GJXLA
DQQUQ VBCHW MOETP DYTXJ UVXRS LCELV WDGMN TLSJI ULADO WAESF
KDZIC TKVHV QORWU ZONPD QDRZX DBSAA PTRXT RZUPK BEKKV IBHDB
YOQVM KQBCY XEAAB OLCXV XGRGO JZKSP NNRWL XJMJR HOFJN IBUVY
EVRIU CJWZY RGPDL BSJJA KNHNG ISBGA BJTED GQJQE NUTNT FTSIG
JPRTY ATTXQ MOXWN BPRBN NQTKN NZBGV SDOCV UYBDQ EVOGX BRBAH
BIRMK LKBUR ZOTGO EOCPI BBQAH PKMIJ VKPQX PAPEK AYEED UQJRE
KPZSY IRPPT EUTKR EIOYQ YARZJ QRIVM SRIQN AMAOF PPRTF DLMQE
GGTWN CQUVK TLVUD XJFXK MIDTY LYRMP TMWVC MGGHK KIJPL MOJRW
TNSJR VEXWS FKFRE RSTII FLKTS GZMXK ZMFMP XCEGA BJSBS XADAR
MTCAR DMWIY ZJQAN UUODZ DMXSJ IWXUT RIWBE KNCFQ FVRYV YPXXC
TLADG UCNDL YIJWT GHBOE RAGYI XZFWS MKLHW YJTED WJEUI UYENQ
OAEOG ZVGRF KEKVN YFQCI TWQQM DEVRV JKXIY BINAJ ZRMEJ XWEIB
HKQYL IWPMP IAYNU OCBJD JBXPU JYDGH PIJAW BHTPN SXIUU BGPQQ
IECKJ PYVHW YSEUV PNPSK FPEAM THRHZ VNROD FUADM UAAXN YOSTQ
AETHB FFSCN DQEBY VWPIW PYVHD UPBTO WFHET WIYOD FLVKN KASNU
HLOKN FCROX ECXHG YBCPS ELIIC UCQWT KCDYV FYNUX TNQGA PDETF
SUGUX VMWMV TLFLA SDAYJ ATAVV RKHQU AZOSA JQAAX JIRNL CKHYF
EORRY QMAWI EWIHR KWWQE REFVJ VTUIC CNJHK OKHFH ZDQYV ZANGE
OHWRV CWJYW XXDVK IPEVH UKSNY JASAP BVIKH EHOUN QSSFB EVLBM
FYYBP CEXIO MYFHA NKOVU PLPOK XRWVU BRFRY CZIZG CXPOT PFAHX
NGJTV XJJQI VTWXH YWYNX CMHNG JIWBF TZBMU KUJRH ANKOU QVWZK
JVMCH XIVQO VCKTR GFQAV OZJJN SQYOS SBZIB ATUBP IACSW GFBCU
VCJMC GSCMI VKGIE DHTWJ MLQSJ YJQES WTDFM FTCZH TNXOL WCONO
YBDIU DGHPH MEAUZ TNURE GIRKE TWQAY DYPEB QALQS WAAGT ZHDGQ

Cut that out, paste it to one side of a 3 by 5 index card, paste your trigraph on the other side, give a copy to a friend, and you’re ready for some secret communications.

We used the for macro and undigits function from the Standard Prelude, plus a few other functions from the Standard Prelude to build the histogram. You can run the program at http://programmingpraxis.codepad.org/fFmsqWJQ.

Pages: 1 2