3
\$\begingroup\$

I'm new to Go, and as a learning project I've been implementing RC4, attempting to follow pseudo-code in the Wikipedia links (and trying not to look at the far-superior version in the crypto package).

Some questions:

  • Wikipedia suggests computing new array indexes using mod 256 at several points throughout the implementation. However, mod 256 results in index out of bound errors or "constant 256 overflows byte". What am I missing?
  • The crypto package returns a custom "Cipher" type, which has the rc4 function implemented on it. Is this idiomatic Go (returning an objecty type) or something specific for the rc4 implementation?
  • any suggestions to improve clarity/speed/accuracy?

Source:

package main
import "fmt"

func ksa(keystring string) ([256]byte) {
  var key = []byte(keystring)
  var s [256]byte
  var j byte

  for i := 0; i < 255; i++ {
    s[i] = byte(i)
  }
  for i := 0; i < 255; i++ {
    j = (j + s[byte(i)] + key[i % len(key)]) % 255
    s[j], s[i] = s[i], s[j]
  }
  return s
}

func rc4(bufferstring string, key [256]byte) ([]byte) {
  buffer := []byte(bufferstring)
  res := make([]byte, len(buffer))
  var x, y, k, r byte = 0, 0, 0, 0

  for i, b := range(buffer) {
    x = (x + 1) % 255
    y = (y + key[x] % 255)
    y, x = x, y
    k = key[(key[x] + key[y]) % 255]
    r = b ^ k

    fmt.Printf("i: %d, b: %c, x: %#X, y: %#X, k: %#X, r: %#X  \n", i, b, x, y, k, r)
    res[i] = r
  }
  return res
}

func main() {
  keystring := "Secret"
  plaintext := "Attack at dawn"
  key := ksa(keystring)

  encrypted := rc4(plaintext, key)

  unencrypted := rc4(string(encrypted), key)

  fmt.Println("Encrypted")
  fmt.Printf("hex: %#X\n", string(encrypted))
  fmt.Printf("string: %s\n", string(encrypted))


  fmt.Println("Un-Encrypted")
  fmt.Printf("hex: %#X\n", string(unencrypted))
  fmt.Printf("string: %s\n", string(unencrypted))
}
\$\endgroup\$
2
\$\begingroup\$

Here is a simple translation of the Wikipedia RC4 key-scheduling algorithm (KSA) and pseudo-random generation algorithm (PRGA) into Go.

package main

import "fmt"

// Key-scheduling algorithm (KSA)
func ksa(key []byte) []byte {
    s := make([]byte, 256)
    for i := range s {
        s[i] = byte(i)
    }
    j := byte(0)
    for i := range s {
        j += s[i] + key[i%len(key)]
        s[i], s[j] = s[j], s[i]
    }
    return s
}

// Pseudo-random generation algorithm (PRGA)
func prga(message, s []byte) []byte {
    text := make([]byte, len(message))
    i, j := byte(0), byte(0)
    for m := range message {
        i++
        j += s[i]
        s[i], s[j] = s[j], s[i]
        k := s[s[i]+s[j]]
        text[m] = message[m] ^ k
    }
    return text
}

// RC4 stream cipher
// http://en.wikipedia.org/wiki/RC4
func rc4(message, key []byte) []byte {
    return prga(message, ksa(key))
}

func main() {
    testRC4 := []struct {
        key, plain []byte
    }{
        {[]byte("Key"), []byte("Plaintext")},
        {[]byte("Wiki"), []byte("pedia")},
        {[]byte("Secret"), []byte("Attack at dawn")},
    }
    for _, test := range testRC4 {
        cipher := rc4(test.plain, test.key)
        fmt.Printf("%s\n", string(test.key))
        fmt.Printf("%s\n", string(test.plain))
        fmt.Printf("%X\n", cipher)
        fmt.Println(string(rc4(cipher, test.key)) == string(test.plain))
    }
}

Output:

Key
Plaintext
BBF316E8D940AF0AD3
true
Wiki
pedia
1021BF0420
true
Secret
Attack at dawn
45A01F645FC35B383552544B9BF5
true

References:

The Go Programming Language Specification

Integer overflow

Conversions

Mod 256 error:

Constants

There are boolean constants, rune constants, integer constants, floating-point constants, complex constants, and string constants. Character, integer, floating-point, and complex constants are collectively called numeric constants.

A constant value is represented by a rune, integer, floating-point, imaginary, or string literal, an identifier denoting a constant, a constant expression, a conversion with a result that is a constant, or the result value of some built-in functions such as unsafe. The boolean truth values are represented by the predeclared constants true and false. The predeclared identifier iota denotes an integer constant.

Numeric constants represent values of arbitrary precision and do not overflow.

Constants may be typed or untyped. Literal constants, true, false, iota, and certain constant expressions containing only untyped constant operands are untyped.

A constant may be given a type explicitly by a constant declaration or conversion, or implicitly when used in a variable declaration or an assignment or as an operand in an expression. It is an error if the constant value cannot be represented as a value of the respective type.

Operators

Operators combine operands into expressions.

Expression = UnaryExpr | Expression binary_op UnaryExpr .
UnaryExpr  = PrimaryExpr | unary_op UnaryExpr .

binary_op  = "||" | "&&" | rel_op | add_op | mul_op .
rel_op     = "==" | "!=" | "<" | "<=" | ">" | ">=" .
add_op     = "+" | "-" | "|" | "^" .
mul_op     = "*" | "/" | "%" | "<<" | ">>" | "&" | "&^" .

unary_op   = "+" | "-" | "!" | "^" | "*" | "&" | "<-" .

Comparisons are discussed elsewhere. For other binary operators, the operand types must be identical unless the operation involves shifts or untyped constants. For operations involving constants only, see the section on constant expressions.

Except for shift operations, if one operand is an untyped constant and the other operand is not, the constant is converted to the type of the other operand.

For example, the compile error "constant 256 overflows byte" can occur as follows:

b := byte(42)
// constant 256 overflows byte
m := b % 256

The integer literal 256 is an untyped numeric constant. In the expression b % 256, it takes the type (byte) of the other operand b. A byte is an eight-bit unsigned integer that can represent the integers 0 to 255. Therefore, it's an error that the constant value 256 cannot be represented as a value of type byte: "constant 256 overflows byte."

\$\endgroup\$
3
  • \$\begingroup\$ Thanks, any idea why mod 255 was failing in my case? \$\endgroup\$ Sep 23 '13 at 17:57
  • \$\begingroup\$ Ahh just noticed your links \$\endgroup\$ Sep 23 '13 at 18:03
  • \$\begingroup\$ I've revised my answer to include an explanation of the mod 256 error: "constant 256 overflows byte." Mod 255 does not fail. \$\endgroup\$
    – peterSO
    Sep 23 '13 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.