JScriptEncrypt - Technical Specification

Encryption is done in two steps - transliteration, then column transposition.

The encrypted text is actually some permutation of columns, and that permutation is stored in the password.

This document introduces column transposition method, explains how permutation is generated and how the transliteration is done.

1. Column transposition

The plain text is written in block with m rows and n columns. The block is written row by row and read column by column. Before reading, the columns are permuted. Permutation is the secret key.

Permutation is acquired from the password. The columns in the plain text block are numbered from 1 to n. That set with n elements is permuted, and gives the order in which the columns of plain text block are read, thus giving the encrypted text.

P ... the permutation, array of n elements
n ... length of P, or number of columns in the block
m ... number of rows in the block
Q ... plain text
R ... encrypted text
assertion: length of text is m*n
function encrypt
begin
j := 0
for i := 1 to n do
k := P[ i ]
for j := k to m do
R[ j ] = Q[ k ]
k := k + n
j := j + 1
end

In the decryption phase, the encrypted text is written column by column, permuted "in reverse", and read row by row.

P ... the permutation, array of n elements
n ... length of P, or number of columns in the block
m ... number of rows in the block
R ... encrypted text
Q ... plain text
assertion: length of text is m*n
function decrypt
begin
j := 0
for i := 1 to m do X[ P[ i ] ] := i * n;
for i := 1 to n do
    for j := 1 to m do
Q[ j ] := R[ X[ j ] + i ]
j := j + 1
end

2. Generating the permutation

2.1. A cycle

Any permutation can be thought of as a sequence (or product) of transpositions. Transposition means 'swapping two elements'. Set of n elements has

(n-1) + (n-2) + ... + 2 + 1 = n · (n-1)/2

transpositions. This does not include identities - transpositions that do not change position of elements. If all the possible transpositions are ordered in the array

{ T_i }, i = 1, 2, ..., n · (n-1)/2

then any specific permutation can be written as array of indexes of transpositions that were done,

i₁, i₂, ..., i_m, where m is any whole number, 1 <= m <= n · (n-1)/2.

I will call such array of indexes a cycle. Many different cycles can represent one and the same permutation.

2.2. Generating a permutation from a cycle

An array of all possible transpositions is needed in order to generate permutations.

n ... number of elements in the set (length of the permutation)
T˙... matrix with n*(n-1)/2 rows and 2 columns, each row holding one
transposition, transposition being a pair of numbers - positions of elements
that will swap places
function calculate_transpositions
begin
  k := 1
for i := 1 to n do
for j := i + 1 to n do
T[ k, 1 ] := i
T[ k, 2 ] := j
k := k + 1
end

As there are around n² transpositions, it's good idea not to have too many columns in the plain text block, or the array T grows very large, and the above calculation gets very time consuming. However, this reduces the number of possible permutations. Because of the way cycles are generated, 13 is good choice for n. This gives around 6 · 10⁹ permutations.

When all the transpositions are calculated, the permutation P can be generated from the cycle C.

n ... number of elements in the set (length of the permutation)
T ... all the possible transpositions
C ... any cycle (order of transpositions to do)
l ... length of cycle (number of transpositions to do)
assertion: 1 <= C[ i ] <= n*(n-1)/2 for any i.
function permutation
begin
for i := 1 to n do P[ i ] := i
for i := 1 to l do
swap P[ T[ C[i], 1 ] ] and P[ T[ C[i], 2 ] ]
end

2.3. Generating a cycle from a password

The set of all the passwords should be uniformly copied into the set of all the cycles. This way two different passwords cannot give the same encrypted text. This is not possible as there are only n! possible permutations and unlimited number of passwords.

This solution is rather simple: it generates a hash value from the password and uses this value as the seed for a pseudorandom number generator. The generated numbers are indexes of transpositions, the cycle. The same length of cycle is always used, namely 21. As JavaScript uses 32-bit numbers, there are around 4 · 10⁹ possible hash values, and the exact same number of possible cycles. This is why 13 was chosen as number of elements that are permuted - 13! = 6 · 10⁹. There is no sense in having more possible permutations (6 · 10⁹) then there are ways to generate one (4 · 10⁹).

The number generator is described with the following formulae:

x_n+1 = 314159269 · x_n + 907633409

Z ... password
v ... length of the password
h ... calculated hash value
function hash
begin
b := 907633409
a := 65599
h := 0
for i := 0 to v do h := ( h modulo b ) * a + Z[ i ]
end

h ... hash value obtained from the password
n ... number of elements in the set (length of the permutation)
l ... length of cycle (number of transpositions to do)
k ... number of all the possible transpositions
C ... generated cycle
assertion: 1 <= C[ i ] <= k for any i.
function cycle
begin
k := n * ( n - 1 ) / 2
for i := 1 to l do
h := 314159269 * h + 907633409
C[ i ] := h modulo k
end

3. Transliteration

The algorithm reads letters of the source text, starting from position 0 and adds them into the temporary array skipping letters that were already added. Temporary array is full when 7 letters are skipped in a row. Let us assume reading and filling the temporary array stopped at position n in source text.

When the temporary array is full, n letters of the source text are transliterated, starting from position 0. Transliteration is done by replacing the current letter in the source text with it's follower in the temporary array.

Such partial transliteration is repeated, but this time from position n+1.

In the reverse operation, current letter in the source text is replaced by it's predecessor in the temporary array.

S ... source text
D ... destination text
n ... length of text
M ... temporary array
function transliteration
begin
i := 1
j := 1
while i <= n do
k := 0
l := 0
while ( k < 7 ) && ( i <= n ) do
if there is no S[ i ] in M then
M[ q ] := S[ i ]
q := q + 1
k := 0
else
k := k + 1
i := i + 1
while j <= i do
k := (position of S[ j ] in M)
if text is transliterated then
        k := k + 1
if k := q then k := 0
else // reverse
k := k - 1
if k := -1 then k := q
D[ j ] := M[ k ]
end

Tomislav Sereg
8 Mar 2001