Main step of GOST 28147-89: Difference between revisions
m (→{{header|Perl 6}}: use constant) |
(Stronger D entry) |
||
Line 90: | Line 90: | ||
=={{header|D}}== |
=={{header|D}}== |
||
This code is not efficient. |
|||
{{trans|C}} |
{{trans|C}} |
||
{{trans|Go}} |
{{trans|Go}} |
||
⚫ | |||
<lang d>struct GOST { |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
private bool _validateSBox(in SBox data) pure nothrow { |
|||
foreach (ref row; data) |
|||
in { |
|||
foreach ( |
foreach (ub; row) |
||
if (ub >= 16) // Verify it's a nibble. |
|||
return false; |
|||
return true; |
|||
} |
|||
struct GOST(sBoxes...) |
|||
if (sBoxes.length == 1 && _validateSBox(sBoxes[0])) { |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
foreach (i; 0 .. k87.length) { |
foreach (i; 0 .. k87.length) { |
||
// Given |
// Given validateSBox, the & 0xFF aren't necessary. |
||
k87[i] = ((s[7][i >> 4] << 4) & 0xFF) | s[6][i & 0xF]; |
k87[i] = ((s[7][i >> 4] << 4) & 0xFF) | s[6][i & 0xF]; |
||
k65[i] = ((s[5][i >> 4] << 4) & 0xFF) | s[4][i & 0xF]; |
k65[i] = ((s[5][i >> 4] << 4) & 0xFF) | s[4][i & 0xF]; |
||
Line 114: | Line 118: | ||
} |
} |
||
private static uint |
private static uint rol(in uint x, in uint y) pure nothrow { |
||
return |
return (x << y) | (x >> (32 - y)); |
||
} |
|||
⚫ | |||
⚫ | |||
b[0] = u & 0xFF; |
|||
⚫ | |||
b[2] = (u >> 16) & 0xFF; |
|||
b[3] = (u >> 24) & 0xFF; |
|||
} |
} |
||
// Endianess problems? |
|||
⚫ | |||
⚫ | |||
immutable uint y = (k87[(x >> 24) & 0xFF] << 24) | |
immutable uint y = (k87[(x >> 24) & 0xFF] << 24) | |
||
(k65[(x >> 16) & 0xFF] << 16) | |
(k65[(x >> 16) & 0xFF] << 16) | |
||
(k43[(x >> 8) & 0xFF] << 8) | |
(k43[(x >> 8) & 0xFF] << 8) | |
||
k21[ x & 0xFF]; |
k21[ x & 0xFF]; |
||
return (y |
return rol(y, 11); |
||
} |
} |
||
// This |
// This performs only a step of the encoding. |
||
⚫ | |||
// This code is not efficient, and it's not general. |
|||
⚫ | |||
public void mainStep(in ubyte[8] input, in ubyte[4] key) |
|||
⚫ | |||
pure nothrow { |
|||
immutable key32 = toUint(key); |
|||
ubyte[4] aux4 = input[0 .. 4]; |
|||
immutable input1 = toUint(aux4); |
|||
aux4[] = input[4 .. $]; |
|||
immutable input2 = toUint(aux4); |
|||
aux4[] = buffer[0 .. 4]; |
|||
toUbyte4(f(key32 + input1) ^ input2, aux4); |
|||
buffer[0 .. 4] = aux4[]; |
|||
⚫ | |||
} |
} |
||
} |
} |
||
Line 155: | Line 143: | ||
// S-boxes used by the Central Bank of Russian Federation: |
// S-boxes used by the Central Bank of Russian Federation: |
||
// http://en.wikipedia.org/wiki/GOST_28147-89 |
// http://en.wikipedia.org/wiki/GOST_28147-89 |
||
// This is a matrix of nibbles. |
// (This is a matrix of nibbles). |
||
enum SBox cbrf = [ |
|||
[ 4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3], |
[ 4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3], |
||
[14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9], |
[14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9], |
||
Line 166: | Line 154: | ||
[ 1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12]]; |
[ 1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12]]; |
||
// Example from the talk page: |
// Example from the talk page (bytes swapped for endianess): |
||
immutable |
immutable uint[2] input = [0x_04_3B_04_21, 0x_04_32_04_30]; |
||
immutable uint key = 0x_E2_C1_04_F9; |
|||
auto key = cast(immutable ubyte[4])x"F9 04 C1 E2"; |
|||
GOST!cbrf g; |
|||
g.mainStep(input, key); |
g.mainStep(input, key); |
||
writefln("%(% |
writefln("%(%08X %)", g.buffer); |
||
}</lang> |
}</lang> |
||
{{out}} |
|||
<pre>07CF881F 043B0421</pre> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
Revision as of 00:13, 20 October 2012
You are encouraged to solve this task according to the task description, using any language you may know.
GOST 28147-89 is a standard symmetric encryption based on a Feistel network. Structure of the algorithm consists of three levels:
- encryption modes - simple replacement, application range, imposing a range of feedback and authentication code generation;
- cycles - 32-З, 32-Р and 16-З, is a repetition of the main step;
- main step, a function that takes a 64-bit block of text and one of the eight 32-bit encryption key elements, and uses the replacement table (8x16 matrix of 4-bit values), and returns encrypted block.
Implement the main step of this encryption algorithm.
C
Version with packed replacement table.
<lang C>static unsigned char k87[256]; static unsigned char k65[256]; static unsigned char k43[256]; static unsigned char k21[256];
void kboxinit(void) { int i; for (i = 0; i < 256; i++) { k87[i] = k8[i >> 4] << 4 | k7[i & 15]; k65[i] = k6[i >> 4] << 4 | k5[i & 15]; k43[i] = k4[i >> 4] << 4 | k3[i & 15]; k21[i] = k2[i >> 4] << 4 | k1[i & 15]; } }
static word32 f(word32 x) { x = k87[x>>24 & 255] << 24 | k65[x>>16 & 255] << 16 | k43[x>> 8 & 255] << 8 | k21[x & 255]; return x<<11 | x>>(32-11); }</lang>
C++
<lang cpp>UINT_32 TGost::ROL(UINT_32 X, BYTE n) {
_asm{ mov eax, X mov cl, n rol eax, cl
mov X,eax
}
return UINT_32(X); }
UINT_64 TGost::SWAP32(UINT_32 N1, UINT_32 N2) {
UINT_64 N;
N = N1; N = (N<<32)|N2; return UINT_64(N); }
UINT_32 TGost::ReplaceBlock(UINT_32 x) {
register i; UINT_32 res = 0UL; for(i=7;i>=0;i--) { ui4_0 = x>>(i*4); ui4_0 = BS[ui4_0][i]; res = (res<<4)|ui4_0; } return res;
}
UINT_64 TGost::MainStep(UINT_64 N,UINT_32 X) {
UINT_32 N1,N2,S=0UL; N1=UINT_32(N); N2=N>>32; S = N1 + X % 0x4000000000000; S = ReplaceBlock(S); S = ROL(S,11); _asm{
mov eax,N2 xor S,eax
} N2 = N1; N1 = S; return SWAP32(N2,N1);
}</lang>
Variable "BS" is the replacement table.
D
<lang d>alias immutable ubyte[16][8] SBox; // A matrix of nibbles.
private bool _validateSBox(in SBox data) pure nothrow {
foreach (ref row; data) foreach (ub; row) if (ub >= 16) // Verify it's a nibble. return false; return true;
}
struct GOST(sBoxes...) if (sBoxes.length == 1 && _validateSBox(sBoxes[0])) {
private static immutable ubyte[256] k87, k65, k43, k21; private uint[2] buffer;
nothrow static this() { alias sBoxes[0] s; foreach (i; 0 .. k87.length) { // Given validateSBox, the & 0xFF aren't necessary. k87[i] = ((s[7][i >> 4] << 4) & 0xFF) | s[6][i & 0xF]; k65[i] = ((s[5][i >> 4] << 4) & 0xFF) | s[4][i & 0xF]; k43[i] = ((s[3][i >> 4] << 4) & 0xFF) | s[2][i & 0xF]; k21[i] = ((s[1][i >> 4] << 4) & 0xFF) | s[0][i & 0xF]; } }
private static uint rol(in uint x, in uint y) pure nothrow { return (x << y) | (x >> (32 - y)); }
// Endianess problems? private static uint f(in uint x) pure nothrow { immutable uint y = (k87[(x >> 24) & 0xFF] << 24) | (k65[(x >> 16) & 0xFF] << 16) | (k43[(x >> 8) & 0xFF] << 8) | k21[ x & 0xFF]; return rol(y, 11); }
// This performs only a step of the encoding. public void mainStep(in uint[2] input, in uint key) pure nothrow { buffer[0] = f(key + input[0]) ^ input[1]; buffer[1] = input[0]; }
}
void main() {
import std.stdio;
// S-boxes used by the Central Bank of Russian Federation: // http://en.wikipedia.org/wiki/GOST_28147-89 // (This is a matrix of nibbles). enum SBox cbrf = [ [ 4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3], [14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9], [ 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11], [ 7, 13, 10, 1, 0, 8, 9, 15, 14, 4, 6, 12, 11, 2, 5, 3], [ 6, 12, 7, 1, 5, 15, 13, 8, 4, 10, 9, 14, 0, 3, 11, 2], [ 4, 11, 10, 0, 7, 2, 1, 13, 3, 6, 8, 5, 9, 12, 15, 14], [13, 11, 4, 1, 3, 15, 5, 9, 0, 10, 14, 7, 6, 8, 2, 12], [ 1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12]];
// Example from the talk page (bytes swapped for endianess): immutable uint[2] input = [0x_04_3B_04_21, 0x_04_32_04_30]; immutable uint key = 0x_E2_C1_04_F9;
GOST!cbrf g; g.mainStep(input, key); writefln("%(%08X %)", g.buffer);
}</lang>
- Output:
07CF881F 043B0421
JavaScript
<lang JavaScript>function ОсновнойШаг(блок_текста, элемент_ключа) {
var N = блок_текста.slice(0); var X = элемент_ключа; var S = (N[0] + X) & 0xFFFFFFFF; var ячейка; var нов_S = 0; for (var сч = 0; сч < 4; сч++) { ячейка = (S >>> (сч << 3)) & 0xFF; нов_S += (ТаблицаЗамен[сч*2][ячейка & 0x0F] + (ТаблицаЗамен[сч*2+1][ячейка >>> 4] << 4)) << (сч << 3); } S = (((нов_S << 11) + (нов_S >>> 21)) & 0xFFFFFFFF) ^ N[1]; N[1] = N[0]; N[0] = S; return N;
}</lang>
Note: the variable "блок_текста" is an array of two 32-bit values that make up the block.
Glagol
Here the function "БеззнСлжПоМод32" sells unsigned add numbers modulo 232, "ИсклИЛИ" implements bitwise XOR of 32-bit variables, and "Замена" by replacing the specified 4-bit block.
ПЕР
Ключ: РЯД 8 ИЗ ЦЕЛ;
ТаблицаЗамен: РЯД 8, 16 ИЗ ЯЧЦЕЛ;
ЗАДАЧА БеззнСлжПоМод32(ч1, ч2: ЦЕЛ): ЦЕЛ;
ПЕР
память1, память2: ШИРЦЕЛ;
результат: ЦЕЛ;
УКАЗ
память1 := 0; ОБХОД.Образ(ОБХОД.ПолучитьАдрес(ч1), ОБХОД.ПолучитьАдрес(память1), 4);
память2 := 0; ОБХОД.Образ(ОБХОД.ПолучитьАдрес(ч2), ОБХОД.ПолучитьАдрес(память2), 4);
УВЕЛИЧИТЬ(память1, память2);
ОБХОД.Образ(ОБХОД.ПолучитьАдрес(память1), ОБХОД.ПолучитьАдрес(результат), 4);
ВОЗВРАТ результат
КОН БеззнСлжПоМод32;
ЗАДАЧА ИсклИЛИ(ч1, ч2: ЦЕЛ): ЦЕЛ;
УКАЗ
ВОЗВРАТ ОБХОД.Значение(ЦЕЛ, ОБХОД.Значение(МНОЖ, ч1) / ОБХОД.Значение(МНОЖ, ч2))
КОН ИсклИЛИ;
ЗАДАЧА Замена(стр: ЯЧЦЕЛ; яч: ОБХОД.Ячейка): ЯЧЦЕЛ;
ПЕР
п1, п2, п3: ЦЕЛ; результат: ЯЧЦЕЛ;
УКАЗ
п1 := 0; п2 := 0; ОБХОД.Образ(ОБХОД.ПолучитьАдрес(яч), ОБХОД.ПолучитьАдрес(п1), 1);
п1 := Асм.Сдвиг(п1, 4); ОБХОД.Образ(ОБХОД.ПолучитьАдрес(п1), ОБХОД.ПолучитьАдрес(п2), 1);
п2 := Асм.Сдвиг(п2, -4); п1 := Асм.Сдвиг(п1, -8);
п3 := ТаблицаЗамен[стр*2, п2] + Асм.Сдвиг(ТаблицаЗамен[стр*2+1, п1], 4);
ОБХОД.Образ(ОБХОД.ПолучитьАдрес(п3), ОБХОД.ПолучитьАдрес(результат), 1);
ВОЗВРАТ результат
КОН Замена;
ЗАДАЧА ОсновнойШаг(N: ШИРЦЕЛ; X: ЦЕЛ): ШИРЦЕЛ;
ПЕР
N1, N2, S: ЦЕЛ;
сч: ЯЧЦЕЛ;
ячейка: ЯЧЦЕЛ;
результат: ШИРЦЕЛ;
УКАЗ
ОБХОД.Образ(ОБХОД.ПолучитьАдрес(N), ОБХОД.ПолучитьАдрес(N1), 4);
ОБХОД.Образ(ОБХОД.ПолучитьАдрес(N)+4, ОБХОД.ПолучитьАдрес(N2), 4);
S := БеззнСлжПоМод32(N1, X);
ОТ сч := 0 ДО 3 ВЫП
ОБХОД.Образ(ОБХОД.ПолучитьАдрес(S)+сч, ОБХОД.ПолучитьАдрес(ячейка), 1);
ячейка := Замена(сч, ячейка);
ОБХОД.Образ(ОБХОД.ПолучитьАдрес(ячейка), ОБХОД.ПолучитьАдрес(S)+сч, 1)
КОН;
S := Асм.Вращение(S, 11);
S := ИсклИЛИ(S, N2);
N2 := N1; N1 := S;
ОБХОД.Образ(ОБХОД.ПолучитьАдрес(N1), ОБХОД.ПолучитьАдрес(результат), 4);
ОБХОД.Образ(ОБХОД.ПолучитьАдрес(N2), ОБХОД.ПолучитьАдрес(результат)+4, 4);
ВОЗВРАТ результат
КОН ОсновнойШаг;
Go
<lang go>package main
import "fmt"
type sBox [8][16]byte
type gost struct {
k87, k65, k43, k21 [256]byte enc []byte
}
func newGost(s *sBox) *gost {
var g gost for i := range g.k87 { g.k87[i] = s[7][i>>4]<<4 | s[6][i&15] g.k65[i] = s[5][i>>4]<<4 | s[4][i&15] g.k43[i] = s[3][i>>4]<<4 | s[2][i&15] g.k21[i] = s[1][i>>4]<<4 | s[0][i&15] } g.enc = make([]byte, 8) return &g
}
func (g *gost) f(x uint32) uint32 {
x = uint32(g.k87[x>>24&255])<<24 | uint32(g.k65[x>>16&255])<<16 | uint32(g.k43[x>>8&255])<<8 | uint32(g.k21[x&255]) return x<<11 | x>>(32-11)
}
// code above adapted from posted C code
// validation code below follows example on talk page
// cbrf from WP var cbrf = sBox{
{4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3}, {14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9}, {5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11}, {7, 13, 10, 1, 0, 8, 9, 15, 14, 4, 6, 12, 11, 2, 5, 3}, {6, 12, 7, 1, 5, 15, 13, 8, 4, 10, 9, 14, 0, 3, 11, 2}, {4, 11, 10, 0, 7, 2, 1, 13, 3, 6, 8, 5, 9, 12, 15, 14}, {13, 11, 4, 1, 3, 15, 5, 9, 0, 10, 14, 7, 6, 8, 2, 12}, {1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12},
}
func u32(b []byte) uint32 {
return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
func b4(u uint32, b []byte) {
b[0] = byte(u) b[1] = byte(u >> 8) b[2] = byte(u >> 16) b[3] = byte(u >> 24)
}
func (g *gost) mainStep(input []byte, key []byte) {
key32 := u32(key) input1 := u32(input[:4]) input2 := u32(input[4:]) b4(g.f(key32+input1)^input2, g.enc[:4]) copy(g.enc[4:], input[:4])
}
func main() {
input := []byte{0x21, 0x04, 0x3B, 0x04, 0x30, 0x04, 0x32, 0x04} key := []byte{0xF9, 0x04, 0xC1, 0xE2}
g := newGost(&cbrf) g.mainStep(input, key) for _, b := range g.enc { fmt.Printf("[%02x]", b) } fmt.Println()
}</lang>
- Output:
[1f][88][cf][07][21][04][3b][04]
Perl 6
Implemented to match explanation on Discussion page:
<lang perl6># sboxes from http://en.wikipedia.org/wiki/GOST_(block_cipher) constant sbox =
[4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3], [14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9], [5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11], [7, 13, 10, 1, 0, 8, 9, 15, 14, 4, 6, 12, 11, 2, 5, 3], [6, 12, 7, 1, 5, 15, 13, 8, 4, 10, 9, 14, 0, 3, 11, 2], [4, 11, 10, 0, 7, 2, 1, 13, 3, 6, 8, 5, 9, 12, 15, 14], [13, 11, 4, 1, 3, 15, 5, 9, 0, 10, 14, 7, 6, 8, 2, 12], [1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12];
sub infix:<rol³²>(\y, \n) { (y +< n) % 2**32 +| (y +> (32-n)) }
sub ГОСТ-round(\R, \K) {
my \a = (R + K) % 2**32; my \b = :16[ sbox[$_][(a +> (4*$_)) % 16] for 7...0 ]; my \c = b rol³² 11; c;
}
sub feistel-step(&F, \L, \R, \K) {
(R, L +^ F(R, K))
}
my @input = 0x21, 0x04, 0x3B, 0x04, 0x30, 0x04, 0x32, 0x04; my @key = 0xF9, 0x04, 0xC1, 0xE2;
my ($L,$R) = @input.reverse.map: { :256[$^a,$^b,$^c,$^d] }; my ($K ) = @key\ .reverse.map: { :256[$^a,$^b,$^c,$^d] };
($L,$R) = feistel-step(&ГОСТ-round, $L, $R, $K);
- reproduce example output from Discussion page
say (((($L +< 32 + $R) +> (8*$_)) % 256).fmt('[%02X]') for 0..7).join;</lang>
- Output:
[1F][88][CF][07][21][04][3B][04]
Tcl
<lang tcl>namespace eval ::GOST {
proc tcl::mathfunc::k {a b} {
variable ::GOST::replacementTable lindex $replacementTable $a $b
}
proc mainStep {textBlock idx key} {
variable replacementTable lassign [lindex $textBlock $idx] N0 N1 set S [expr {($N0 + $key) & 0xFFFFFFFF}] set newS 0 for {set i 0} {$i < 4} {incr i} { set cell [expr {$S >> ($i * 8) & 0xFF}] incr newS [expr { (k($i*2, $cell%15) + k($i*2+1, $cell/16) * 16) << ($i * 8) }] } set S [expr {((($newS << 11) + ($newS >> 21)) & 0xFFFFFFFF) ^ $N1}] lset textBlock $idx [list $S $N0] return $textBlock
}
}</lang> Note that only the idx'th row of the split-up textBlock (which contains the two pieces to intermingle/exchange at this step) is altered; it is the responsibility of the caller to iterate over all the steps through the entire plaintext/ciphertext.
X86 Assembly
Parameter in the call:
- EAX - the youngest part of the transformed block (N1);
- EDX - leading part transformed block (N2);
- ESI - address of the first element of the key;
- EBX - table address changes;
- ECX - the number of major steps.
Output results:
- EDX = N1, EAX = N2 for cycles 32-З, 32-Р;
- EAX = N1, EDX = N2 for cycle 16-З.
Register Usage: all except EDI.
Notes:
- At the end of the run the registers as follows:
- EBX (pointer to table of changes) - the same as that in the early
- ESI (pointer to key) - points to the first byte of the key - it's N * 4 larger than the initial values for the SI cycle reps N (for encryption cycles N = 32 => 4 * N = 128, for authentication code generation cycle N = 16 => 4 * N = 64), larger than the initial values for the authentication code generation cycle.
- ECX = 0
- The contents of the segment registers unchanged.
<lang Asm> .386
.model flat .code
_gost32 proc near32
public _gost32
- The inner loop of a subroutine
- 1. Beginning of the cycle, and preservation of the old N1
iloop: mov EBP,EAX
- 2. Adding to the S key modulo 2^32
add EAX,[ESI] ; add the key add ESI,4 ; the next element of the key.
- 3. Block-replace in the rotation of S by 8 bits to the left
REPT 3
xlat ; recoding byte ror EAX,8 ; AL <- next byte add EBX,100h; next node changes
ENDM
xlat ; recoding byte sub EBX,300h; BX -> 1st node changes
- 4. Complete rotation of the S at 3 bits to the left
rol EAX,3
- 5. The calculation of the new values of N1,N2
xor EAX,EDX mov EDX,EBP
- The completion of the inner loop
loop iloop ret
_gost32 endp
end</lang>