HP-16C Encryption Algorithm « Next Oldest | Next Newest »

 ▼ John Williamson Junior Member Posts: 2 Threads: 1 Joined: Jan 1970 01-18-2006, 07:56 PM Here's a slightly unusual HP-16C program -- it's an encryption program based around the shrinking linear feedback register (lfsr) stream cipher (see Wikipedia's article of the SLFSR). The program takes plaintext blocks and a key and encodes (or decodes) a message. This algorithm is particularly suited to the 16c, where variable length registers are easy to deal with, and a bit count instruction is available (the feedback of an lfsr can be computed at bitcount(state&tap)&1). Running the encryption on the calculator makes it very difficult for a potential adversary to tamper with the device or the program to weaken this system -- it's also very portable (and deniable, for the truly paranoid). Unfortunately, this algorithm is slow, it takes about a minute to encrypt a 64 bit block. The cipher key should specify the lengths of 2 lfsrs, which should be between about 30 and 64 (max) bits each. The two lsfrs should be different lengths (the periods -- which are [2^(len) - 1] -- should be mutually prime for maximum effectiveness). Each length should be stored, as a 64 bit word, in register C and D respectively. The key should also specify the feedback polynomial to be used. Some example polynomials are given in the table at the end of this message. The two polynomial codes should be stored in register 2 and 9 respectively, with WSIZE set to the width of the appropriate lfsr. The key should finally give the initial state of the lfsr's, and again with WSIZE set to the width of the lfsr, these should be placed in registers 1 and 8. To ensure security, you should generate two sequences of random digits (one for each lfsr) for each new message transmitted, and xor them with the original lfsr state as specified with the key. These digits must be noted and prepended [unencrypted] to the start of the transmitted message. This ensures that each run will not use identical keys. Encryption proceeds by storing the first 64 bits of plaintext in register E, and executing GTO 0 then R/S. The output will be stored back in register E. The next 64 bits should be stored in E, and the algorithm repeated until the entire message has been completed. Decryption is identical, using the encoded messages as the plaintext. Here's an example usage session which should make things clearer (maybe): Given a key ```len1 len2 poly 1 poly 2 state 1 state2 0x21 0x29 0x1b7536ba 0x1d56e7fe0fd 0xbb72d45d 0xb1bb10ff ``` imagine we want to encrypt the message HELLO WORLD. Rewriting this as alphabet indices, 31=space, we have ```8 5 12 12 15 31 23 15 18 12 4 ``` We could code this as 5 bit blocks and concatenate (which is more efficient), but I'll just use 8-bit blocks here, so we have two 64 bit message blocks: ```08 05 0c 0c 0f 1f 17 0f 18 0c 04 00 00 00 00 00 ``` OK, to set up the encryption with this key, execute ```(1) HEX/40/WSIZE 21 STO C (sets length of lfsr1) (2) 29 STO D (sets length of lfsr2) (3) 21/WSIZE/1b7536ba STO 2 (sets tap poly. for lfsr 1) (4) 10bfea/ENTER (random digits just made up for this message, note these for later) (5) bb72d45d/XOR/STO 1 (sets state for lfsr 1) (6) 29/WSIZE/1d56e7fe0fd STO 9 (sets tap poly. for lfsr 2) (7) a10786/ENTER (again, randomly chosen for this message, take a note of them for transmission) (8) b1bb10ff/XOR/STO 8 (sets state for lfsr 2) ``` Now, the system is set up and we can encrypt messages! So do 40/WSIZE/08050c0c011f170f/STO E (this is the first part of the message we created above) GTO 0/R/S. After some time, we get the encrypted version back. Note this down. Then do 180c040000000000/STO E/GTO 0/R/S to encrypt the next part (and so on, if we had more blocks to do). The message to transmit is then just the random digits we made up in (7) and (8), plus the outputs after each run. Decryption is identical, just use the initial digits from the start of the message in steps (7) and (8) instead of creating new ones, and put the encoded message in E and run it... SECURITY NOTE: This is currently thought to be reasonably secure (though there are some existing attacks, none are currently practical, needing large amounts of ciphertext (>4gb) with known poly. tap sequences). This cipher will probably not stop a dedicated government agency, but it will stop most others, for now, and it's the only one I could fit on the 16c! Any comments or suggestions for optimization are most welcome. ```; Shrinking LFSR encryption ; storage register use: ; 1 -- lfsr1 state (n1 bits) ; 2 -- lfsr1 taps (n1 bits) ; 8 -- lfsr2 state (n2 bits) ; 9 -- lfsr2 taps (n2 bits) ; b -- counter variable (64 bits) ; c -- length of lfsr 1 (64 bits) [n1] ; d -- length of lfsr 2 (64 bits) [n2] ; e -- plaintext (64 bits) ; note: strange things can happen with registers overlapping ; with different wsizes. if lfsr1 is much longer than lfsr2, it's ; possible lfsr1 will overlap with lfsr2 and break everything. Don't ; use lfsr of wildly different widths and you should be fine. encrypt:lbl 0 ; entry point 0 wsize ; ensure 64 bit mode hex ; hex mode cf 4 ; clear carry 4 0 ; 0x40 = 64 decimal sto b ; store loop count encloop:lbl 1 1 sto i ; lfsr1 starts at reg 1 rcl c ; get length for lfsr1 gsb 2 ; gsb [lfsr] execute lfsr starting w/register 1. result in carry 0 rlc ; shift carry into 1's position sto f ; store lfsr1 output bit into B (from carry) 8 ; sto i ; lfsr2 starts are register 8 rcl d ; get length for lfsr2 gsb 2 ; gsb [lfsr] execute lfsr starting w/register 4. result in carry f? 4 ; check the carry state (lfsr output) gsb 3 ; gsb [wrt] if it was one, use this bit to encrypt f? 4 ; check carry state (1 if bit was used) x!=0 ; if carry, test b>0, else jump unconditionally gto 1 ; goto encloop rtn ; finished! ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; compute an lfsr lfsr: lbl 2 wsize ; set register len rcl (i) ; get lfsr state from i[1] isz ; i++ rcl (i) ; tap from i[2] and ; b# ; compute popcount(tap&lfsr) & 1 ; (only last bit will be shifted into carry ; implied &1) rrc ; rotate the result into the carry dsz ; i-- rcl (i) ; get lfsr state from i[1] rrc ; rotate (output) carry onto end sto (i) ; store state back 0 ; wsize ; set size back to 64 bits rtn ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Write -- encrypts one bit of plaintext wrt: lbl 3 ; encrypt one bit of the plaintext rcl e ; recall the plaintext rcl f ; the output bit from first lfsr xor ; xor the first bit rr ; rotate round (after 64 rotates, each bit will have been xor'd once) sto e ; store back again rcl b 1 - sto b ; decrement loop counter sf 4 ; set carry ;;;;;;;;;;;;;;;; end of listing ``` ```Here's a short table of feedback polynomials: ---------------- bits(decimal) polynomial(hex) 33:975b2bb7 33:1b7536ba5 33:dd4bc39 33:70f4aec1 33:7e713745 33:8bb239f9 41:165e4698745 41:fc1ff9daaf 41:1d56e7fe0fd 46:3032a9a7b4dd 46:189e7d51e93d 46:1e4bc55f3c8d 46:25309c48243b 46:2e12091c8653 50:1499b99e86fcd 50:19fb0bccecc95 50:6128a518f6b3 50:26b78c528a431 50:19f727b474c9 50:99716f277cc1 50:72c5d02ac5dd 62:485b1bd4de7a81f 62:3c0af3d95ec6d091 62:18c7880c6d09658d 62:18d3485b1808f18d 62:1a369332db7d4793 62:24f15f6da664b62d 64:16991084bfd25227 64:c89497fa421132d1 64:862bc20fc33f97b ``` I have a much larger set of tables at http://www.dcs.gla.ac.uk/~jhw/poly-hex.zip. ▼ John Noble Member Posts: 56 Threads: 1 Joined: Jan 2007 01-19-2006, 01:43 AM Fascinating! Very nicely presented, too -- some of it may have penetrated my thick skull. I don't pretend to understand encryption, but the fact that you did such a thing on a machine like a 16C is just too cool. Hmmm... I wonder if the supposedly simple Rijndael algorithm (AKA AES) could fit on a 16C? There have been ports to, among other things, Atmel AVR micros. If I understand the problem correctly, however, the minimum 128 bit block lengths might chew up too much of a 16C's resources. Thanks for a great read. ▼ Les Bell Senior Member Posts: 540 Threads: 22 Joined: Jan 2005 01-19-2006, 03:39 AM John, I suspect that the use of S-boxes (effectively a kind of 2D lookup table) in algorithms like AES, as well as DES et al, rules them out for a limited-memory device like the 16C. I'd love to be proved wrong, though. ;) Best, --- Les [http://www.lesbell.com.au] ▼ John Williamson Junior Member Posts: 2 Threads: 1 Joined: Jan 1970 01-19-2006, 05:45 AM The S-Box is a problem for AES, but the values can be computed for each entry in the table according to a fairly simple set of bit operations, except you need to compute inverses in GF(256). Given an short algorithm to do that, the S-Box entries could be computed on the fly. In this way, you would probably need 2 or 3 8-bit registers for temporary storage and 12 32-bit registers (4 each for plaintext, key and state), leaving 150 bytes for the code. But the key schedule seems to need 8 32 bit words as a buffer, as far as I can see, which is not possible on the 16c. The substitute/shiftrow/mixcols/addkey steps are maybe possible, but the key schedule is probably the biggest stumbling block for an 16c implementation.

 Possibly Related Threads... Thread Author Replies Views Last Post Bought a 16C to compensate a little Eelco Rouw 23 4,106 12-07-2013, 01:26 PM Last Post: Eelco Rouw Shiny new 16C! Keith Midson 7 1,398 10-27-2013, 02:22 AM Last Post: Keith Midson Joys of eBay: HP-32S, HP-32SII, HP-42S, HP-16C, ... Sasu Mattila 7 1,320 09-23-2013, 04:39 PM Last Post: Julián Miranda (Spain) HP-16C simulator fhub 12 1,921 06-30-2013, 10:14 PM Last Post: Robert Prosperi Program for HP-16c... Leonid 9 1,507 06-07-2013, 08:51 PM Last Post: David Hayden HP 11C/12C/15C/16C case Philippe Cairic 4 1,168 11-06-2012, 06:04 PM Last Post: Matt Agajanian Understanding HP-16C integer division Jimi 18 2,755 10-16-2012, 09:13 PM Last Post: Eddie W. Shore Question about a "combinations" algorithm Namir 9 1,353 09-20-2012, 04:51 PM Last Post: Gilles Carpentier Linear Programming - Simplex Algorithm LarryLion 5 970 09-04-2012, 10:57 PM Last Post: David Hayden Hack a 15C-le into a 16C? David Griffith 20 2,797 12-23-2011, 07:00 AM Last Post: robert rozee

Forum Jump: