RC4 implementation in Go 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 &lt; 255; i++ {
    s[i] = byte(i)
  }
  for i := 0; i &lt; 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))
}
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  = "||" | "&amp;&amp;" | rel_op | add_op | mul_op .
rel_op     = "==" | "!=" | "&lt;" | "&lt;=" | "&gt;" | "&gt;=" .
add_op     = "+" | "-" | "|" | "^" .
mul_op     = "*" | "/" | "%" | "&lt;&lt;" | "&gt;&gt;" | "&amp;" | "&amp;^" .

unary_op   = "+" | "-" | "!" | "^" | "*" | "&amp;" | "&lt;-" .

  
  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."