Implementing Galois Field Multiplication

Galois Field multiplication is commenly used in cryptoraphy, some of them like Rijndael (AES) and serpent are employing Galois Field GF(2⁸) as one of its cryptographic component.

Galois Field multiplication by two is actually left shift with conditional XOR by the modulo constant. If the most significant bit of the value that being multiplied is two, then we have to XOR the result by the modulo constant.

For example, Rijndael (AES) uses Galois Field Multiplication with modulo constant = 0x1b. Below are two versions of Galois Field implementation intended for two different family of PICMicro microcontroller.

Example: Suppose we want to get 2*W alog GF(2⁸) using modulo constant 0x1b (Rijndael/AES)

Low End and Mid Range Microcontrollers

gf	movwf	tmp
	bcf	status,c
	rlf	tmp,w
	btfsc	status,c
	xorlw	0x1b
	return

High End Microcontrollers

gf	rlncf	wreg,w
	btfsc	wreg,0
	xorlw	(0x1b ^ 0x01)
	return

Fibonacci Number Generator on PIC16F84

This morning, i wrote simple code for generating fibonacci number on PIC16F84 Microcontroller. The calculation was based on 128-bit binary addition. The largest generated fibonacci number was 3.328511 x 10³⁸ which actually the 186-th fibonacci number. I released this code under the GNU Free Documentation License.

The source code is available here. This code was taken from my blog specified on embedded cryptography.

Implementing Lookup Table

Lookup table is one of important things in microcontroller, it is commonly used many application for many purposes. This is true since lookup table is able to emulate encoding, decoding, substitution and many other application.

Please note that you have to be aware of page boundary issue while doing lookup table. The rule is that the starting address of lookup table plus the size of lookup table should not exceed page boundary, not only that, the index of lookup table also must not exceed table size.

In low end and mid range PICmicro microcontroller, page boundary size is 256 byte. For some reason, you might need to do page alignment first using "org ($+0xff)&~0xff".

There are many types of doing lookup table, this example below will show you how to do lookup table. Here we assume that lookup table does not cross page boundary.

Example : Simple Lookup table


movlw 0x05 ; initialize lookup index
call lookup ; do lookup
movwf myreg ; save the result on myreg

lookup:
andlw 0x0f ; normalize index to 0x0f
addwf pcl,f
dt 0x12,0x45,0x7c,0x5a,0x81,0x99,0x74,0xa4
dt 0xc6,0x2d,0x97,0x34,0x12,0x05,0x3d,0xf1


Implementing Select Case Branching

Suppose, you are facing situation where you have code a program such that your microcontroller is able to make a decision based on arbitrary value i.e. using select case. There is better way to do this rather than doing subtracting one by one.

The keyword here is about exploting the properties of XOR operation and also the properties of zero flag on PICmicrocontroller. First, that XORing two indentical value results zero that trigger zero flag. Second, that XOR has a property such that A XOR B XOR C XOR A equal to B XOR C. From those two concept, we can derive effective way of doing select case function. See this example below.

Suppose we wish to implement this pseudo code below:

W = myreg
if (myreg == '0x10') then goto sub1
if (myreg == '0x43') then goto sub2
if (myreg == '0x62') then goto sub3


well, the code above is adopted for PICmicro microcontroller as follow:

movf myreg,w ; copy myreg to W
xorlw 0x10
btfsc status,z ; check 0x43
goto sub1
xorlw 0x53 ; 0x53 = 0x10 XOR 0x43
btfsc status,z ; check for 0x43
goto sub2
xorlw 0x31 ; 0x31 = 0x10 XOR 0x43 XOR 0x62
btfsc status,z
goto sub3


Tricky Circular Shift

If you had a problem of doing circular shift on PICmiro microcontroller especially for mid range and low end microcontroller such PIC10Fxx PIC12Fxx and PIC16Fxx, hopefully this trick will help you.

It is true that low end and mid range PICmicro microcontroller does not provide such a specific instruction to do circular shift. Low end and mid range PICmicro microcontrollers keep doing shift through carry bit, buy there is a way of doing this. The keyword is about copying the bit that is going to be passed through carry. Lets go directly to example.

Example 1: 8-bit circular left shift by one

rlf myreg,w ; copy MSB to carry bit
rlf myreg,f ; circular left shift myreg


Example 2: 8-bit circular right shift by one

rrf myreg,w ; copy LSB to carry bit
rrf myreg,f ; circular left shift myreg


Example 3: 8-bit circular left shift by two

rlf myreg,w ; copy MSB to carry bit
rlf myreg,w ; do circular left shift twice
rlf myreg,w ;
movwf myreg ;


Example 4: 8-bit circular right shift by two

rrf myreg,w ; copy LSB to carry bit
rrf myreg,w ; do circular right shift twice
rrf myreg,w ;
movwf myreg ;


Example 5: 16-bit circular left shift by one

rlf myreg_h,w
rlf myreg_l,f
rlf myreg_h,f


Example 6: 16-bit circular left shift by one

rrf myreg_l,w
rrf myreg_h,f
rrf myreg_l,f


Example 7: 32-bit circular left shift by one

; myreg = [myreg3 | myreg2 | myreg1 | myreg0]
rlf myreg3,w
rlf myreg0,f
rlf myreg1,f
rlf myreg2,f
rlf myreg3,f


That's it, hopefully you can grasp the concept. You can also extend this way for larger circular shifting.

On the fly 2's complement conversion

In PICmicro microcontroller, converting an arbitrary binary number to its 2's complement is really easy to do. That process is done by only executing an instruction. Not only that, by exploiting the properties of 2's complement, we can also implement fast way to get 2's complement of a number. I'll tell you the concept.

2's complement of a = 0 - a

The operation above can simply emulated using sublw 0x00 instruction. That is true since we knew that the real operation of sublw 0x00 is just w = 0 - w. See this example below:


movlw 0x0a ; fill W with 10 decimal
sublw 0x00 ; convert W's content to 2's complement


Hopefully this small trick helps you :)

Setting bits in register W

In PICmicro, you can easily set and reset any register file bits by simply executing bcf and bsf instruction. What if you need to set certain bits in W register, is there any way to do this? The answer is yes. Although there is no such insruction to directly set any bits in W register, we can trick this situation by exploiting the characteristics of bitwise OR boolean function.

If a bit is ORed by "1", you will see that that bit will set to one, no matter what it was. In the other side, ORing with "0" will result nothing. Well, lets exploit this properties to solve our problem.

I'll show you some examples, it will help you to grab the concept intuitively.


iorlw b'00000100' ; set bit 2 of W register
iorlw b'10000000' ; set bit 7 of W register


Thats it, simple right. This is because PICmicro gave us flexibility in software manipulation and that is the one that make PICmicro powerfull.