CRYPTOLOGIA

http://dx.doi.org/10.1080/01611194.2016.1260666

Mathematical problems of the Second International

Students’ Olympiad in Cryptography
S. Agievich, A. Gorodilova, V. Idrisova, N. Kolomeec, G. Shushuev,
and N. Tokareva

ABSTRACT KEYWORDS
A detailed overview of the mathematical problems and their Boolean functions;
solutions for the Second International Students’ Olympiad in competition; NSUCRYPTO;
Cryptography (NSUCRYPTO’2015) is given. The authors Olympiad
consider mathematical problems related to the construction
of special discrete structures associated with cryptographic
applications, highly nonlinear functions, points on an elliptic
curve, crypto machines, solving the Diffie-Hellman problem,
performing any bijective mapping on a binary tape,
modifications of ciphers, and so forth. Some unsolved
problems are also discussed.

1. Introduction
Mathematical problems occupy a special place in cryptography. It is
well-known that mathematical ideas and results often serve as a stimulus
for the creation of modern cryptographic systems. Here, one can mention
concepts of public-key cryptography, algebraic foundations of many
symmetric ciphers, applications of cryptographic Boolean functions,
and so on. It is worth mentioning that the language of cryptography is
rather mathematical.
In this article, we discuss mathematical problems from the Second
International Students’ Olympiad in Cryptography (NSUCRYPTO’2015)
(www.nsucrypto.nsu.ru). It is an annual event devoted to mathematics in
cryptography without restrictions: It is held via the Internet, is comprised
of unsolved mathematical problems, and is open to professionals as well as
for students and senior pupils.
One should note that there are several school competitions in cryptography
such as the Interregional Olympiad in Mathematics and Cryptography for
high school students (www.cryptolymp.ru), the Olympiad in Mathematics

CONTACT N. Tokareva [email protected] Laboratory of Discrete Analysis, Sobolev Institute of

Mathematics, Novosibirsk State University, pr. ac. Koptyuga 4, Novosibirsk 630090, Russia.
Color versions of one or more of the figures in the article can be found online at www.tandfonline.com/ucry.
© 2017 Taylor & Francis
2 S. AGIEVICH ET AL.

and Cryptography for high school students of Belarusian State University

(www.uni.bsu.by/arrangements/kripto/), and so forth. Cryptographic tasks
can also be found at main and preparatory stages of the International Olym-
piad in Informatics for school students, for example at the Australian national
preparatory stage Burton (2008). Numerous competitions in the area of infor-
mation security, called Capture The Flag (CTFs) (www.ctftime.org/ctfs), com-
petitions for breaking codes and solving ciphers, such as Alan Turing
cryptography competition (http://www.maths.manchester.ac.uk/cryptogra-
phy_competition) for students from the United Kingdom, National Cipher
Challenge University of Southampton (www.cipher.maths.soton.ac.uk/), and
mysterious Cicada 3301 puzzles (Bell 2013) can be found worldwide.
NSUCRYPTO is the unique cryptographic Olympiad containing scientific
mathematical problems for students and professionals from any country. Its
aim is to involve young researchers in solving curious and tough scientific
problems of modern cryptography. From the very beginning, the concept of
the Olympiad was not to focus on solving olympic tasks but on including
unsolved research problems at the intersection of mathematics and
cryptography.
In this article, we provide a detailed overview of the mathematical problems
of the Olympiad.
We start with the registration process and the description of rounds.
Then, we discuss all 17 mathematical problems of the Olympiad and
their solutions. Among them, there are both amusing tasks based on
historical ciphers and hard mathematical problems. We consider
mathematical problems related to the construction of special discrete
structures associated with cryptographic applications, highly nonlinear
functions and points on an elliptic curve, crypto machines, solving the
Diffie-Hellman problem, performing any bijective mapping on a binary
tape, modifications of ciphers, and so forth. Some unsolved problems
are also discussed.
The organizers of the Olympiad are Novosibirsk State University, Sobolev
Institute of Mathematics (Novosibirsk), Tomsk State University, Belarusian
State University, and University of Leuven (KU Leuven, Belgium). More than
700 participants from 24 countries registered on the website of the Olympiad,
(www.nsucrypto.nsu.ru). The list of winners can be found in the last part of
this article.
The mathematical problems of the First International Olympiad
NSUCRYPTO’2014 can be found in Agievich and colleagues (2015).
 CRYPTOLOGIA 3

2. Organization and rules of the Olympiad

Here, we briefly formulate the key points of the Olympiad.

Rounds of the Olympiad. There were two independent Internet rounds.
The first round (duration 4 hours 30 minutes) was individual and consisted
of two sections: school (section A) and student (section B). It was held on
16 November. Theoretical problems in the mathematics of cryptography
were offered to participants. The second round (duration 1 week; 17–24
November) was devoted to research and programming problems of
cryptography, solved in teams.
Everybody could participate! To become a participant of the Olympiad, it
was necessary and sufficient to register on the website (www.nsucrypto.nsu.
ru). There were no restrictions on the status or age of participants. Participants
from all countries were welcome. During the registration, every participant had
to choose a corresponding category: “senior pupil” (for pupils and school stu-
dents), “student” (for participants who were currently studying at universities),
or “other/professional” (for participants who already completed their education
or just want to be in the restriction-free category). There were particular prizes
for each category, respectively, so if you were a pupil of some school you should
have chosen the category “senior pupil” during registration because you would
have had higher chances of winning in it.
The first round was divided into sections: A and B. The problems of section
A were prepared for participants from the “senior pupil” category, and the
problems of section B were offered for participants from categories “student”
and “other/professional.” The second round was general for all participants.
Language of the Olympiad. All problems were given in English.
Format of the solutions. We accepted solutions in any electronic format
(pdf, jpg, txt, rtf, docx, tex, etc). For example a participant was able to write
his solutions on paper and send us a picture. Solutions should have been
written with all necessary details.
4 S. AGIEVICH ET AL.

Prizes. There were several categories of prizes:

. For senior pupils: winners of section A of the first round;
. For students: winners of section B of the first round;
. For participants in the category other/professional: winners of section B of
the first round;
. For participants (for every category separately): winners of the second
round; and
. Special prizes from the Program Committee, if one proposes a correct
solution of the problem marked as unsolved.

3. Problem structure of the Olympiad

The Olympiad was comprised of 17 problems. Some of them were included in
both rounds.
Thus, the school section of the first round consisted of six problems,
whereas the student section contained seven problems. Three problems were
common to both sections. The following table shows the highest score one
could get for solving each problem.
Problems of the first round (A: school section)

N Problem title Maximum scores

1 Key sharing 4
2 RSA numbers 4
3 Bigrams 4
4 An encryption table 4
5 Crypto street 4
6 An elliptic curve 8

Problems of the first round (B: student section)

N Problem title Maximum scores

1 An encryption table 4
2 Crypto street 4
3 An elliptic curve 10
4 Give an answer 4
5 A binary tape 6
6 Covering radius 4
7 The machine DH-d 10

The second round was composed of ten problems; they were common to all
the participants. Two of the problems presented in the second round were
marked as unsolved (and to be awarded special prizes from the Program
Committee).
 CRYPTOLOGIA 5

Problems of the second round

N Problem title Maximum scores

1 A secret sharing Unsolved
2 The machine DH-d 10
3 A modification of PRESENT 6
4 Guess the cipher 4
5 Hypothesis Unsolved
6 A binary tape 6
7 Palindrome cipher 10
8 Highly nonlinear functions 8
9 Covering radius — 2 8
10 Bigrams 4

4. Problems
4.1. Problem “Key sharing”
A bank safe can be opened with nine keys inserted in its keyholes in the right
order. The keyholes are arranged in a circle. The order of keys is right if the
sum of the keys (each key is associated with a natural number) in every three
consecutive keyholes is divisible by 3.
The safe has two special features: If you insert a key in a keyhole, you
cannot get it back until all nine keys are inserted; if the order of the nine
inserted keys is wrong, the safe sends the “SOS signal” and blocks itself.
The keys are shared by three people: Alice, Bob, and Caroline. All together
they can insert their keys in the right order and then open the bank safe. Their
keys are the following:
– Alice: {4,14,24};
– Bob: {34,44,54};
– Caroline: {64,74,84}.
Today, Alice, Bob, and Caroline are going to open the safe. One of them for-
got the rule of the right order for the keys and has already inserted two of his
keys into consecutive keyholes, when he was stopped by his friends. Prove that
Alice, Bob, and Caroline still are able to open the safe in this situation.

4.2. Problem “RSA numbers”

RSA is one of the most popular cryptosystems with a public key. We know
that it operates with two big prime numbers p and q that should be kept secret
by each user.
Eve is a malefactor who likes to steal the secret RSA parameters of users
and then sell them via the Internet. Today, she sells a new pair of primes p
and q satisfying the following relation:
p4x þ 4 � 2015 ¼ q4y for some natural numbers x and y.
Should the clients of Eve buy these numbers?
6 S. AGIEVICH ET AL.

4.3. Problem “Bigrams”

Users of a communication system send messages to each other. Every message
is written in English. Eve is a malefactor who intercepts messages in this chan-
nel and replaces them with new ones. In detail, she does the following: inter-
cepts a message, removes all spaces and punctuation marks from it, and splits
the message into bigrams starting from the beginning. Then, she makes several
iterations of message destruction. The number of iterations is random.
All bigrams are divided into three types:
I. Bigram that contains only vowels (e.g., A A , E I , I O , U O , Y U , …).
II. Bigram that contains only consonants (e.g., B N , T R , L L , P W, S D , …).
III. Bigram that contains one vowel and one consonant (e.g., Q A , E C ,
H I , K O , …).
For each iteration, Eve takes two random bigrams B1 and B2 of different
types and removes them from the message; at the same time, she adds a
new random bigram B3 of the third type at the beginning of the message. If
she chooses bigrams of types I and II (II and III; I and III), she will add an
arbitrary bigram of type III (I; II).
For example, the message C R Y P T O T E X T can be transformed by Eve in the
following way:
CRYPTO TEXT ! ðCRÞðYPÞðTOÞðTEÞðXTÞ ! ðOEÞðCRÞðTOÞðTEÞ ! ðFEÞðTOÞðTEÞ

The question is the following. You know that Alice has sent the following
message to Bob
THE MEETING WILL TAKE PLACE AT THREE IN EEYORE EAGLE BEE CREEK INN

The message has been intercepted by Eve. She has repeated iterations of
destruction until only one bigram remained. Could it be a bigram consisting
of one vowel and one consonant?

4.4. Problem “An encryption table”

Mary read a book about the history of cryptography and found an interesting
cipher. It encrypts messages consisting of letters from the English alphabet (26
letters from “A ” to “Z ”). For encryption, one must choose a codeword of
length n in the English alphabet and construct an encryption table T of size
n × n in the following way. The first column is filled by the letters of the
chosen codeword. Then, each row is filled by letters in alphabetical order
starting with the letter in the first cell.
The message is encrypted letter by letter. The ciphertext for a message of
length t consists of t ordered pairs of integers (i, j), where i is the row number
and j is the column number in the table T of a current letter.
An example. Let the codeword be MA R Y . Then the ciphertext for the
message C R Y P T O is (2,3) (3,1) (4,1) (1,4) (3,3) (1,3).
 CRYPTOLOGIA 7

For the message R S A , the ciphertext could be (3,1) (3,2) (2,1) or (3,1) (3,2) (4,3).
Mary has encrypted a sentence using this cipher. As a result, she got the
following ciphertext, where all spaces in the text are preserved unchanged:
ð8; 1Þ ð7; 8Þ ð1; 1Þ ð2; 6Þ ð5; 5Þ ð7; 5Þ ð11; 7Þ ð7; 8Þ ð5; 7Þ ð8; 11Þ ð9; 1Þ ð3; 1Þ
ð6; 1Þ ð7; 5Þ ð7; 6Þ ð7; 5Þ ð1; 10Þ ð2; 5Þ ð7; 5Þ ð7; 4Þ ð2; 7Þ ð11; 2Þ ð3; 9Þ ð1; 11Þ
ð6; 3Þ ð7; 8Þ ð7; 5Þ ð11; 6Þ ð7; 9Þ ð1; 5Þ ð9; 8Þ ð1; 4Þ ð7; 5Þ
ð3; 1Þ ð5; 9Þ ð6; 4Þ ð8; 8Þ ð5; 10Þ ð7; 5Þ ð3; 11Þ ð9; 1Þ ð1; 8Þ ð7; 8Þ ð7; 5Þ ð9; 10Þ
Try to read it given that the codeword was 11 letters in length, the encryption
table contained all English letters, and its fragment was the following:

M N O
S T U
R S T

4.5. Problem “Crypto street”

You are walking near Novosibirsk State University and its new hostels with a
secret message in hand. Can you read it? (Note that a colored picture is
available at www.nsucrypto.nsu.ru.)
8 S. AGIEVICH ET AL.

4.6. Problem “Give an answer”

Two young friends Roman and Stephan use a method to communicate with
each other without exchanging common secret keys. Their messages consist of
letters from the following extended English alphabet: �A �, �B �, … ,
�Z �, �0 �, �1 �, …, �9 �, � �, �? �, �.�.
Here is a fragment of their recent dialog:

Stephan to Roman : Q2A?4FV4GOCX4IASOXF?K4AJSKN?CXK4NOSK6T

Roman to Stephan : AXOLNJ42?K4QOXUJ4IN4804JA7S
They supposed that nobody could understand their dialog, but surprisingly
Stephan recieved the message
2?K4AJVKN2LXKS4OF42OM4SAQ7KX
from their classmate Anton, and Stephan easily understood it!

Try to read the chat!

And what would be your answer?

4.7. Problem “Covering radius”

In order to protect a new block cipher against some attacks based on S-box
approximations, Alice must solve the following problem.
Let Fn2 be an n-dimensional vector space over the field F2 ¼ {0, 1}. Let
n ¼ 2k, where k is a positive integer. Evaluate the covering radius, and
describe the metric complement of the linear subspace spanned by the rows
of the following k × n matrix:
0 1
1 0 ... 0 0 ... 0 1
B 0 1 ... 0 0 ... 1 0 C
B .. .. C
B
M ¼ B... ... . ... ...C
0
. ... ... C ¼ ðIk =Ik Þ;
@ 0 ... 1 0 0 1 ... 0 A
0 ... 0 1 1 0 ... 0
where Ik is the identity k × k matrix and I 0k is its copy flipped horizontally.
Remark I. Recall several definitions and notions. A set L � Fn2 is called a
linear subspace if for every x, y 2 L the sum x � y is also in L. The Hamming
distance d(x, y) between vectors x; y 2 Fn2 is defined as the number of
positions where they differ, that is, d(x, y) ¼ |{i | xi ≠ yi}|. The Hamming
distance from a vector y to a subset X � Fn2 is defined as d(y, X) ¼ minx2X
d(y, X). Since the distance between any two vectors is bound by n, for an
arbitrary subset X there is the number d(X) such that
 CRYPTOLOGIA 9

– For every y 2 Fn2 , it holds that d(y, X) ≤ d(X);

– There is a vector z 2 Fn2 with d(z, X) ¼ d(X).
This number is called the covering radius of X. The set
X ¼ fz 2 Fn2 j dðz; XÞ ¼ dðXÞg is called the metric complement of X.
^
Remark II. Let us consider several examples:
– Let X consist of a single vector x 2 Fn2 . It is easy to see that d(X) ¼ n and
X^ ¼ fx � 1g, where 1 is the all-ones vector;
– Let Y be a ball of radius r centered at x: Y ¼ fy 2 Fn2 j dðx; yÞ � rg. One can
verify that d(Y) ¼ n − r and Y ^ ¼ fx � 1g:

4.8. Problem “Guess the cipher”

There was a cipher, N S U C R Y P T O ’2 0 1 5 , that encrypted messages written in
the 26-letter English alphabet from A to Z . A message length did not exceed
50 letters. Participants had access to the page www.nsucrypto.nsu.ru/archive/
2015r2/task4 where the encryption algorithm was implemented, and they
could get the ciphertext for any of their correct input messages. The task
was to describe this cipher.

4.9. Problem “A binary tape”

A cipher machine works with a binary infinite tape that starts with an input
word of length n, and all its other elements are zero. The machine encrypts an
input word and writes the result instead of it.
The cipher machine can perform two operations:
1. Copy any symbol on the tape to another position;
2. Apply a fixed one-to-one function S : Fm 2 ! F2 to the first m symbols,
m

where F2 ¼ {0, 1}.

The same sequence of operations (the encryption program) is applied to all
input words of length n. Find the conditions for S so that the machine can
perform any bijective mapping of words of length n.
Examples of operations.
1. For instance, the machine can copy the third symbol to the fifth place:
1 1 1 0 0 0 1 1 1 …

The result will be

1 1 1 0 1 0 1 1 1 …

2. Let m be 3 and S(x, y, z) ¼ (x, y, x � z); applying S to the first three symbols:
1 1 1 0 0 0 1 1 1 …

The result will be

1 1 0 0 0 0 1 1 1 …
10 S. AGIEVICH ET AL.

4.10. Problem “A modification of P R E S E N T ”

Peter decided to modify the well-known cipher P R E S E N T .
At first, we give a description of P R E S E N T according to the article
“PRESENT: An Ultra-Lightweight Block Cipher” by A. Bogdanov and
colleagues (2007).
It is a classical substitution-permutation network (SP-network) that
consists of 31 rounds with the block size equal to 64 bits and the key size equal
to 80 bits. Each of the 31 rounds consists of an XOR operation to introduce a
round key Ki for 1 ≤ i ≤ 32, where K32 is used for post-whitening, a non-linear
substitution layer, and a linear bitwise permutation P. The non-linear layer
uses a single 4-bit S-box S which is applied 16 times in parallel in each round.
addRoundKey. Given the current s t a t e b63 … b0 and round key
K i ¼ ki63 ki62 � � � ki0 for 1 ≤ i ≤ 32, a d d R o u n d K e y consists of the operation
bj ! bj � kij for 0 ≤ j ≤ 63.
sBoxlayer. The S-box is a permutation from F42 to F42 . For s B o x L a y e r the
current s t a t e b63 … b0 is considered as sixteen 4-bit words w15 … w0 where
wi ¼ b4·i+3||b4·i+2|| b4·i+1||b4·i for 0 ≤ i ≤ 15 and the output nibble S[wi] pro-
vides the updated s t a t e values in the obvious way. The action of this box
in hexadecimal notation is defined by the following table.
x 0 1 2 3 4 5 6 7 8 9 a b c d e f
S(x) c 5 6 b 9 0 a d 3 e f 8 4 7 1 2

pLayer. The bit permutation is defined by the table. Bit i of s t a t e is

moved to bit position P(i).

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
P(i) 0 16 32 48 1 17 33 49 2 18 34 50 3 19 35 51
i 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
P(i) 4 20 36 52 5 21 37 53 6 22 38 54 7 23 39 55
i 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
P(i) 8 24 40 56 9 25 41 57 10 26 42 58 11 27 43 59
i 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
P(i) 12 28 44 60 13 29 45 61 14 30 46 62 15 31 47 63

The key schedule. The user-supplied key is stored in a key register K and
represented as k 79k 78 … k 0. At round i, the 64-bit round key Ki ¼ k63k62 … k0
consists of the 64 leftmost bits of the current contents of register K . Thus, at
round i, we have Ki ¼ k63k62 … k0 ¼ k 79k 78…k 16. After extracting the round
key Ki, the key register K ¼ k 79k 78…k 0 is updated as follows. The key register
is rotated by 61 bit positions to the left, then the left-most four bits
k 79k 78k 77k 76 are passed through the P R E S E N T S-box, and finally the
r o u n d - c o u n t e r value i is XORed with bits k 19k 18k 17k 16k 15 of K with
the least significant bit of r o u n d - c o u n t e r on the right.
 CRYPTOLOGIA 11

What Peter has modified:

. In sBoxlayer, he changed S-box to the following
x 0 1 2 3 4 5 6 7 8 9 a b c d e f
S(x) c 8 d 1 e a 7 b 4 0 5 9 6 2 f 3

. In pLayer, he applied permutation P3 instead of P.

. In the key schedule, he rotated the key register by 16 bit positions to the
left instead of 61. He used his new S-box from sBoxlayer here.
. Finally, he reduced the number of rounds to 15.
As a result, Peter got the new cipher P e t e r - P R E S E N T . Below, you can
find examples of test vectors for P e t e r - P R E S E N T that are given as integers
in hexadecimal notation.

plaintext key ciphertext

0000000000000000 00000000000000000000 f 778777b0774f 772
ffffffffffffffff 00000000000000000000 888708847883888d
0000000000000000 ffffffffffffffffffff 7f f 8f f f b0f f c7f f a
ffffffffffffffff ffffffffffffffffffff 00078004700b0005

Peter states that his modification is rather good, but his friend Mark does
not think so. He claims that it is enough to get only two pairs �plaintext–
ciphertext � (P1, C1), (P2, C2), where Ci ¼ P e t e r - P R E S E N T (Pi, K), i ¼ 1,
2, and K is the unknown key, for reading any message C encrypted with this
key K in the ECB mode.
Peter decides to argue with Mark and presents the following pairs, where P1
and P2 form the message ! N S U C R Y P T O - 2 0 1 5 ! (ASCII codes of letters and
little-endian order of bytes are used to form 64-bit integers as the inputs
b63b62 … b0):
!NSUCRYP ! P1 ¼ 5059524355534e21 ! C1 ¼ 2ddbf038b201448f
TO 2015! ! P2 ¼ 21353130322d4f54 ! C2 ¼ d4bf134bd57f4df2
He asks Mark to read the secret message whose ciphertext C is
C ¼37aa471c953defe1 91aa595c0236edc9 80f10a020c33e5cb
ddf14e15923df8dc 8cf8470d027af1db 9caa061e9537ead1
92e10a1e072ea2c0 d1f1501e9b27f2c3 94e750140134e386
92f6595b093de3d2 99ec435b0235ebdc 83ef4b099b37f886
9eef461e4f76eecf 9eaa4912093df8d2 ddf15e129231f8c7
89ec45184f3ee4cf 94e25e5b9c36eddc 87e55a0b9221a2d2
ddae471d0e36a2d2 9aec4b159533efca 98e5495b0b34eb86
9cf643180e34ffc3 89aa4c124f21e4c9 ddf6594ad57aefce
dbfb500e9b34efc5
Can Mark win the argument?
12 S. AGIEVICH ET AL.

4.11. Problem “Highly nonlinear functions”

One of the interesting classes of one-to-one vectorial Boolean functions of
the form F : Fn2 ! Fn2 , where n is even, is the set of functions such that
F−1 ¼ F. Does this class contain a function with nonlinearity not less than
2n−1 − 2n/2?
Remark. Recall several definitions.
– A vectorial Boolean function F : Fn2 ! Fn2 can be represented as the set
of its n coordinate Boolean functions: F ¼ (f1, f2, …, fn), where
f 1 ; � � � ; f n : Fn2 ! F2 ;
– The Hamming distance dist(f,g) between two Boolean function f ; g : Fn2
! F2 is equal to the number of vectors x 2 Fn2 such that f(x) ≠ g(x);
– Nonlinearity nlF of F is equal to
min min distðb � F; ‘a;c Þ
b2Fn2 ;b6¼0 a2Fn2 ;c2F2

where b · F ¼ b1f1 � b2f2 � … � bnfn and ℓa,c(x) ¼ a1x1 � a2x2 � … �

anxn � c.

4.12. Problem “Covering radius — 2”

In order to protect a new block cipher against some attacks based on S-box
approximations, Alice must solve the following problem.
Let Fn2 be an n-dimensional vector space over the field F2 ¼ {0, 1}. Let
n ¼ 2k, where k is a positive integer. Evaluate the covering radius and describe
the metric complement of the linear subspace spanned by the rows of the
following k × n matrix:
0 1
1 1 1 0 0 0 0 0 ��� ��� ��� 0
B0 0 1 1 1 0 0 0 ��� ��� ��� 0C
B C
B0 0 0 0 1 1 1 0 ��� ��� ��� 0C
M¼B B .. .. .. C
. . . C
B C
@0 ��� ��� ��� ��� ��� ��� 0 1 1 1 0A
1 0 ��� ��� ��� ��� ��� 0 0 0 1 1
Remark I. Recall several definitions and notions. A set L � Fn2 is called a
linear subspace if for every x, y 2 L, the sum x � y is also in L. The Hamming
distance d(x, y) between vectors x; y 2 Fn2 is defined as the number of posi-
tions where they differ, that is, d(x, y) ¼ |{i | xi ≠ yi}|. The Hamming distance
from a vector y to a subset X � Fn2 is defined as d(y, X) ¼ minx2Xd(y, x).
Since the distance between any two vectors is bounded by n, for an arbitrary
subset X there is the number d(X) such that
– For every y 2 Fn2 , it holds d(y, X) ≤ d(X);
– There is a vector z 2 Fn2 with d(z, X) ¼ d(X).
 CRYPTOLOGIA 13

This number is called the covering radius of X. The set X

^ ¼ fz 2 Fn2 j dðz; XÞ ¼
dðXÞg is called the metric complement of X.
Remark II. Let us consider several examples:
– Let X consist of a single vector x 2 Fn2 . It is easy to see that d(X) ¼ n and
X^ ¼ fx � 1g, where 1 is the all-ones vector;
– Let Y be a ball of radius r centered at x: Y ¼ fy 2 Fn2 j dðx; yÞ � rg. One can
verify that d(Y) ¼ n − r and Y ^ ¼ fx � 1g:

4.13. Problem “An elliptic curve”

Bob develops a new cryptosystem based on elliptic curves. An elliptic curve
determines the set of points (x, y), satisfying the equation y2 ¼ x3 + ax + b
for some fixed real numbers a, b. For the system, Bob chooses the curve y2 ¼
x3 + 56x + 6 and must find all integer points on this curve, that is points (x, y),
where x and y are both integer numbers. Help Bob do this!

4.14. Problem “The machine D H - d ”

Let G be a cyclic group of a large prime order q and g be a generator of G.
Tom designed the machine D H - d that on input (g, gx) outputs gx . Here, gx
d

is an arbitrary element of G, and d is a small fixed positive integer.

Use the machine D H - d to solve the Diffie-Hellman problem (Diffie and
Hellman, 1976), that is, find gxy from (g, gx, gy). Suggest a solution with the
minimal number of requests to the machine.

4.15. Problem “Palindrome cipher”

The company Palindrome had been using the block cipher D E S (National
Bureau of Standards, 1977) to encrypt its documents for the 12 years since
its foundation until its engineers made the decision to use the block cipher
B l o wf i s h (Schneier, 1994) in addition to D E S . It was in 2005. Up to
now, all its documents are encrypted by D E S , and then the result is also
encrypted by B l o wf i s h . The encryption is conducted in ECB mode.
Both ciphers D E S and B l o wf i s h have the same key and block lengths
equal to 64 bits (the descriptions of these ciphers can be easily found).
As a result of information leakage, which occurred during the celebration
of the anniversary of the company, the text of a greeting card leaked to the
Internet. The text of the greeting card was
D e a r c o l l e a g u e s ! C o n g r a t u l a t i o n s f o r o u r wo n d e r f u l
j o u r n e y o f 2 0 y e a r s o f s u c c e s s a n d we h o p e t h e s a me f o r
t he f ut ur e al s o!
14 S. AGIEVICH ET AL.

The ciphertext for that greeting card was

C ¼83c100497b13525e fc8d3201d58ab9ed f6820425912ce184
23034db7b4408629 4df36ca87ad39f4a 99277e6f1e217dfd
f2eab13d1161e849 0fe72e9b98fc1e8a 0aa5680e3b4022cb
4e44c8745afae37f bd5d6d49292bd1b2 9386f2f383061bfd
ae8fca32e6745687 565d353f3bbb1204 aa79742f7ab55fb1
123e6cf37fbad6fe
Could you decrypt the following ciphertext that was intercepted in the
company network a few weeks ago?
C ¼cf414505b7d3aee3 36f48ae753ec799c fb49aaea17fa2a38
2992ed164e9622aa 0b64549dad59a803 0b93be9baf9339e6
fe9780d39168bdff 10d77405d1b51a6a 5475ddf991ef3ad9
85a6c0c451b75da5 aa4c59ec0c40af09 852b70cebeb127b9
43c362dccbebf21e dbb2b086aba67212 1c92e2f327a03b05
b1affd236d8e0f9c 62386237b27597b4 cbe8ec78b07f4ce6
It is known that an encryption 128-bit encryption key is changed dynami-
cally every day according to certain rules, and it is always a sequence of 128
bits where each of the 16 bytes is given by ASCII codes for the figures from 0
to 9 . The first 64 bits form a D E S key, and the other 64 bits form a B l o w-
f i s h key. The parity bits of the DES key are to be ignored.
Here, we present some technical information of the company encryption.
Below, you can find examples of test vectors for combination of both ciphers
D E S and B l o wf i s h . They are given as 64-bit integers b63b62 … b0 in hexa-
decimal notation.
plaintext D E S key B l o wf i s h key ciphertext
0000000000000000 0000000000000000 0000000000000000 561543527d054ad0
0000000000000000 0000000000000000 ffffffffffffffff df 27adaec8337f 57
0000000000000000 ffffffffffffffff 0000000000000000 11148646af 0d82e9
ffffffffffffffff 0000000000000000 ffffffffffffffff 18708bdc3837046f
6c6f 632072616544 3837363534333231 3132333435363738 72e66b26309de78c

To form a 64-bit integer b63b62 … b0, each consecutive eight symbols of an

original text (or key) are transformed into their ASCII codes and little-endian
order of bytes is used.
For example, let us encrypt the message D e a r c o l l e a g u e s ! using the
keys 1 2 3 4 5 6 7 8 and 8 7 6 5 4 3 2 1 for D E S and B l o wf i s h , respectively.
We divide it into two blocks of eight symbols D e a r c o l and l e a g u e s ! ,
and encrypt them separately:
 CRYPTOLOGIA 15

Dear col ! P1 ¼ 6c6f632072616544 ! DES ! T 1 ¼ cb32b921efe674e5 !

! Blowfish ! C1 ¼ 72e66b26309de78c
leagues! ! P2 ¼ 217365756761656c ! DES ! T 2 ¼ f3d9c5f0cf2e9e8f !
! Blowfish ! C2 ¼ 2d9f9fd83b15ae75
Thus, the ciphertext is 7 2 e 6 6 b 2 6 3 0 9 d e 7 8 c 2 d 9 f 9 f d 8 3 b 1 5 a e 7 5 .

4.16. Problem “Hypothesis” (Unsolved)

Prove the following hypothesis, or find a counterexample to it.
Hypothesis. For all n ≥ 2, there exists a Boolean function g : Fn2 1 ! F2 in
the disjunctive normal form, where every variable appears not more than one
time, so that a binary sequence {u1, u2,…} produced for all t ≥ 1 from the
initial state u1,…, un according to the following rule
utþn ¼ ut � gðutþ1 ; utþ2 ; � � � ; utþn 1 Þ
has the maximal possible period equal to 2n.
Remark I. A Boolean function g in m variables is given in a disjunctive nor-
mal form if g(x1,…, xm) ¼ A1_ … _Ak, where Ai is a conjunction of variables
or their negations, i ¼ 1,…, k.
Remark II. In the table, the functions g that confirm the hypothesis for
small n are presented.
n the examples of g(x1, …, xn−1)
2 1
3 x1 _ x2
4 x1 _ x2 x3 ; x1 _ x2 _ x3
5 x 2 _ x 1 x3 x 4 ; x1 _ x 2 x 3 _ x 4

4.17. Problem “A secret sharing” (Unsolved)

Alice, Bob, and Caroline are going to create a secret sharing system. They
choose a subset M � Fn2 and want to share a secret element u from M in
the following way: The secret is represented as x � y � z where x, y, z are
different elements of M ¼ Fn2 nM; Alice, Bob, and Caroline will store x, y,
and z, respectively. Here, Fn2 is the set of all binary vectors of length n.
To use the system, the sets M and M should satisfy the following
conditions:
1. Each element u 2 M can be represented as u ¼ x � y � z, where x, y, z are
different elements of M;
2. For all different x; y; z 2 M, it is right that x � y � z 2 M.
Help them to implement the system suggesting an explicit construction of
the set M for an arbitrary n.
16 S. AGIEVICH ET AL.

5. Solutions of the problems

Here, we discuss the solutions of the problems. Special attention is paid to the
solutions of the participants (right/wrong and beautiful).

5.1. Problem “Key sharing”

Solution. Consider remainders modulo 3 of all sets. There are all possible
remainders (1, 2, and 0) in the set of each person. Hence, it does not matter
who exactly forgot the rule, they are still able to open the safe in the following
way: If the remainders of the two inserted keys are {0,1}, then the necessary
sequence of keys (in terms of remainders) is {0,1,2,0,1,2,0,1,2}. It is obvious
that such a sum is divisible by 3. The same can be done with all possible pairs
of remainders.
This task was completely solved by 15 senior pupils, and they all used the
fact that each person possesses the entire set of possible remainders. Another
five participants offered partial solutions.

5.2. Problem “RSA numbers”

Solution. This problem can be solved in various ways. One interesting and
nontrivial solution was sent by participant Alexandr Evpak (SESC NSU,
Novosibirsk). Let us consider it.
Since p and q are prime numbers, and it holds
p4x þ 4 � 2015 ¼ q4y ;
q4y p4x ¼ ðq2y p2x Þðq2y þ p2x Þ ¼ 8060;
ðqy px Þðqy þ px Þðq2y þ p2x Þ ¼ 4 � 5 � 13 � 31;
we get that p and q are odd numbers. The following relations hold: 2 | (qy −
px), 2 | (qy + px) and 2 | (q2y + p2x), then their product is divisible by 8, but
8060 is not divisible by 8, so the answer should be negative.
The most widespread idea from the sent solutions was to consider the
residue modulo 3 of both equation’s sides. Let us provide a beautiful solution
by Vladimir Schavelev (Gymnasium 6, Novosibirsk):
Let A ¼ p4x and B ¼ q4y. Look at both sides of the equation modulo 3:
A + 2 ¼ B. It is known that a perfect square and 2 can not be congruent
modulo 3. If A � 0 mod 3, then B � 2 mod 3, that is not the case. If A � 1
mod 3, then B � 0 mod 3, hence 3 divides B and q ¼ 3, since q is a prime
number. We can note that B � 1 mod 8, hence A ¼ B − 4 · 2015 � 1 − 4 � 5
mod 8. But the number in degree 4y and 5 can not be congruent modulo
8, so we should not buy these numbers from Eve.
 CRYPTOLOGIA 17

This task was solved by 18 senior pupils, but unfortunately, a few

participants did not check all possible variants of the primes because they
did not consider small numbers.

5.3. Problem “Bigrams”

Solution. We split this sentence into bigrams:
T H E ME E T I N G WI L L T A K E P L A C E A T T H R E E I N E E Y O R E - E A G L E -
B E E C R E E K I N N →( T H ) ( E M) ( E E ) ( T I ) ( N G ) ( WI ) ( L L ) ( T A ) ( K E )
( P L ) ( A C ) ( E A ) ( T T ) ( HR ) ( E E ) ( I N) ( E E ) ( Y O) ( R E ) ( E A ) ( GL ) ( E B )
( E E ) ( CR) ( E E ) ( K I ) ( NN)
We have the following number of bigrams of each type:
Bigrams I: 8 ( E E , E A , E E , E E , Y O , E A , E E , E E )
Bigrams II: 9 ( T H , N G , L L , P L , T T , H R , G L , C R , N N )
Bigrams III: 10 ( E M, T I , WI , T A , K E , A C , I N , R E , E B , K I )

The parity of the sum Bigrams I and Bigrams III is invariant, because if
B1 ¼ Bigram I, B2 ¼ Bigram III, their sum is reduced by 2 and the parity is
not changed, if B1 or B2 ¼ Bigram II, the sum is not changed. In the
beginning, this sum is even, so if the number of Bigrams III is equal to
1, then the number of Bigrams I is not equal to 0, so the answer is
negative.
Nineteen participants completely coped with this problem, and some of
them wrote the code, which allows one to obtain the final state (one vowel
and one consonant) from the initial state.

5.4. Problem “An encryption table”

Solution. Since we are provided with a fragment of the encryption table, we
could try to find a part of the codeword by filling each row with letters to the
left (MS R are hardly the part of a word).

E F G H I J K L M N O
K L M N O P Q R S T U
J K L M N O P Q R S T

The only suitable part seems to be I O N , and it is likely to be the end of the
codeword. Thus, we know rows 9 to 11 of the encryption table. If we suppose
that letter T is before I O N , then the first word of the ciphertext could be T H . .
that corresponds to the codeword …… A T I O N . It allows us to recover the
eighth ciphertext word S I . P . E to S I MP L E and get the first letter I of the
codeword. Step by step, we easily decrypt the whole ciphertext T H I S ME T H O D
18 S. AGIEVICH ET AL.

I S R E F E R R E D T O A S T H E S I MP L E S Q U A R E C I P H E R and the codeword

I NS P I R A T I ON.
This problem was completely solved by almost all participants (by 107 out
of 117 students, by 8 out of 12 professionals, and by 16 out of 30 senior
pupils). Note that many participants started to solve this problem applying
another approach. They noticed that (7,5) is the most frequent letter in the
ciphertext and supposed it to be E . This observation (being Mary’s mistake
in choosing the codeword) helped them to find other letters of the codeword
by analyzing the fourth and seventh words . E F E . . E D and . H E . As a result,
they decrypted the whole ciphertext.

5.5. Problem “Crypto street”

Solution. Notice that the total number of floors is equal to the number of col-
umns in the given text. We have four types of rectangular windows: red,
green, blue, and yellow. Dark and circle-shaped windows are to be considered
as spaces. Hence, starting from the bottom-left corner of the text (letter B ), we
write all the letters in a few rows depending on colors. In such way, we obtain
the row with red windows, the row with blue windows, and so one. The
answer is:
Yellow: I L O V E D Y O U : A N D , I T MA Y B E , F R O M MY S O U L
Green: T H E F O R ME R L O V E H A S N E V E R G O N E A WA Y ,
Red: B U T L E T I T N O T R E C A L L T O Y O U MY D O L E ;
Blue: I WI S H N O T S A D D E N Y O U I N A N Y WA Y .

This is a part of a famous poem written by Alexander Pushkin and translated

by Yevgeny Bonver.
This problem was solved by 37 students, three professionals, and six senior
pupils. They all used this basic approach to cope with the task. A few parti-
cipants read only rows, tinted in particular color, so their solutions were
not finalized.

5.6. Problem “Give an answer”

Solution. We can obtain the following information from the problem con-
dition: The friends have used an asymmetric cryptosystem, and the length
of their alphabet is 39 ¼ 3·13. This brings to mind the idea that the RSA
algorithm has been used, which is also supported by the names of the friends:
Roman, Stephan, Anton. Thus, if the RSA modulus n ¼ 39, then u(n) ¼ 24,
where u is Euler’s totient function, and the only encryption/deciphering
exponents that could be correct are 1, 5, 7, 11, 13, 17, 19, 23. Simple analysis
shows that there are four pairs of equivalent exponents: 1 and 13, 5 and 17, 7
and 19, 11 and 23. Moreover, the encryption and deciphering exponents
 CRYPTOLOGIA 19

coincide with each other. So, we must consider only three nontrivial
exponents. As a result, we get that Roman’s public key is 11, and Stephan’s
public key is 5. The chat was the following:
Stephan to Roman: WH A T I S Y O U R F A V O R I T E A D V E N T U R E N O V E L ?
Roman to Stephan: A R O U N D T H E WO R L D I N 8 0 D A Y S .
Anton to Stephan: T H E A D V E N T U R E S O F T O M S A WY E R

The problem was solved by eight students, but none of them used the
solution described above; they found the answer by applying frequency
analysis only. They said that different substitution ciphers were used without
explaining why there were no secret keys exchanges. The most detailed
solution was provided by Evgeniy Strepetov (Saratov State University). It is
interesting to mention the favorite books of the participants: Treasure Island,
The Mysterious Island, The Children of Captain Grant, The Inhabited Island,
and The Adventures of Tintin.

5.7. Problem “Covering radius”

Solution. Divide all coordinates into pairs like this: (1, n), (2, n − 1), …,
(k, k + 1).
We can say that each pair of coordinates does not depend on the other in
relation to the distance between a vector and the set L, so for arbitrary y 2 Fn2 ,
there is vector x from L such that there is not more than one nonzero element
in each pair of coordinates of y � x, therefore d(X) ≤ k. In fact, d(X) is equal
to k and the metric complement consists of vectors that have only one 1 for
each pair of coordinates.
This problem was solved by nine participants, and they all used a similar
approach. Other solutions of participants were not complete.

5.8. Problem “Guess the cipher”

Solution. The encryption algorithm for N S U C R Y P T O ’2 0 1 5 is the following.
1. The plaintext/ciphertext is a word in the alphabet “ A ” , “ B ” , …, “ Z ” .
2. The length of the ciphertext is twice the length of the plaintext.
3. A random symbol from “ A ” to “ Y ” is prepended to each plaintext symbol.
The obtained pair is transformed into integers p0 2 {0, 1, …, 25}, p1 2 {0, 1,
…, 24}. Then, the integer p ¼ 26p1 + p0 is encrypted in the manner of RSA:
c ¼ p3 mod 667, where the modulus is 667 ¼ 23 · 29.
The ciphertext c is presented as c ¼ 26c1 + c0, both c1, c2 2 {0, 1,…, 25},
and c1, c2 are converted into symbols.
4. The pair of ciphertext symbols is transformed into an integer c. This integer
is decrypted in the following way: p ¼ c103 mod 667.
The plaintext symbol can be recovered using the residue of p mod 26.
20 S. AGIEVICH ET AL.

This problem was solved by many participants, and most of them

solved the problem by obtaining the list of all possible bigrams for each letter
(19 teams proposed the full description).

5.9. Problem “A binary tape”

Solution. Here, we provide the best solution for the problem. It was proposed
by the participant Alexey Udovenko (University of Luxembourg).
Let M(S, x) be the result of running some machine with function S and
input x.
The function is one-to-one, and the domain is equal to the codomain,
therefore the function is a bijection.
1. The first necessary condition is that for the all-zero input, there should be
at least one non-zero output bit of S. Otherwise, the machine will not be
able to compute a single 1-bit (the whole infinite tape is filled with zeros).
This condition allows the machine to get a constant 1-bit.
2. Let us assume that S is an affine function, that is, that it can be represented
as S(x) ¼ Ax + b, where A is a m × m matrix over F2, b is a binary vector of
length m. At each step of the machine, each bit is an affine combination of
some input bits. Therefore, for example, M(S, 00) � M(S, 10) ¼ M(S, 01) �
M(S, 11). It is impossible to compute a mapping such that M(S, 11) ≠ M(S,
00) � M(S, 10) � M(S, 01). Hence, S is not affine.
We now prove that these two conditions are sufficient. We will use the fact
that any function Fm 2 ! F2 can be uniquely represented as an ANF, that is, as
a multivariate polynomial with variables from F2.
1. Consider some input c0 2 Fm 2 with a zero bit in some position. Let c1 be
equal to c0 with that bit set to 1. For some c0, some output bit of S(c0) is
equal to 1, and the same output bit of S(c1) is equal to 0. Indeed, we start
with x ¼ 0m. We know that S(0m) ≠ 0m. We will set bits to 1 one-by-one to
make x equal to S−1(0m). Then, assign c1 ¼ x ¼ S−1(0m), and let c0 be equal
to x without the last setting of 1-bit. Therefore, flipping this bit from 0 to 1
flipped some output bit from 1 to 0.
This means that we can fix c0 except that zero bit and compute a Boolean
NOT function.
2. Since S is not affine, some of the output bits contain a term of degree
d ≥ 2 in its ANF. We let d − 2 variables be equal to 1, and then we will
have a function F22 ! F2 with a term of degree 2 in its ANF. This ANF
may contain other terms. Up to renaming the input variables and then up
to applying the NOT function, the possible ANFs are ab and ab + a. Note
that the second one is equal to a(b + 1), therefore we can apply NOT to
the variable b and get the function with the ANF ab, that is, the Boolean
function AND.
 CRYPTOLOGIA 21

Since the machine now has two primitive functions NOT and AND, every
Boolean function can be computed and any vectorial Boolean function as well.
Therefore, the necessary and sufficient conditions are (1) S(0m) ≠ 0m; (2) S is
not affine.
Other full solutions were proposed by Alexey Miloserdov, Nikita Odinokih,
Saveliy Skresanov (Novosibirsk State University), and Samir Godzhaev, Ravil
Khisamov (Lomonosov Moscow State University).

5.10. Problem “A modification of P R E S E N T ”

Solution. There are several ways to solve this problem. We describe one
method that does not include recovery of the unknown secret key. At first,
from Peter’s modifications we get the following facts:
1. The permutation P3 is the identity, so there is no permutation layer in
P e t e r - P RE S E NT .
2. The new S-box has the representation S(x, y, z, t) ¼ (1 � x � y·z � y·t, 1 �
t, y, z). Thus, its last three coordinate functions are affine and independent
from the input variable x.
Let P ¼ p63p62 … p0, C ¼ c63c62 … c0 and P0 ¼ p063 p062 . . . p00 , C0 ¼ c063 c062 . . . c00
be two pairs of plaintext and ciphertext obtained with the same unknown key
K. The two facts above easily imply that we have the equality
p4�iþj � c4�iþj ¼ p04�iþj � c04�iþj for all i ¼ 0, …, 15 and j ¼ 0, 1, 2. Thus, given
only one pair of known plaintext and ciphertext, that is (P, C), and another
ciphertext C0 , we can obtain 75% of the bits of the corresponding plaintext
P0 . Additionally, since ASCII code is used, we can suppose that bits p08�iþ7
are equal to 0 for all i ¼ 0, …, 7.
To decrypt the ciphertext from the problem condition, we must vary eight
unknown bits in each block and analyze the combinations of letters obtained.
It can be easily done by applying a computer program, and the only readable
text is the following:
G e o r g e B o o l e ’ s l e g a c y s u r r o u n d s u s e v e r y wh e r e , i n t he
c o mp u t e r s , i n f o r ma t i o n s t o r a g e a n d r e t r i e v a l , el ec-
t r oni c ci r cui t s and cont r ol s t hat s uppor t l i f e,
l e a r n i n g a n d c o mmu n i c a t i o n s i n t h e 2 1 s t c e n t u r y.
Using different methods, 11 teams were able to decrypt the secret message
that was devoted to the 200th anniversary of George Boole’s birth on 2
November 2015.
Solutions similar to the one described above were put forth by the teams
from Minsk (Anna Gusakova, Dzmitry Emelyanov, Vadzim Marchuk) and
Prague (Jakub Klemsa, Tomas Jeziorsky, Andrew Kozlik). Note that many
other teams applied another approach and also found the secret key.
22 S. AGIEVICH ET AL.

Their method was based on the fact that Peter’s modification of the key sched-
ule is weak. Namely, we can form four groups of 20 secret key bits that are
independently used to encrypt/decipher four groups of corresponding 16 bits
of plaintext/ciphertext. Thus, given a pair of plaintext and ciphertext, we can
separately solve four tasks with complexity 220 to recover all bits of the
unknown secret key instead of the complexity 280 of brute force.

5.11. Problem “Highly nonlinear functions”

Solution. We provide here the only full solution, proposed by the team
consisting of Alexey Miloserdov, Nikita Odinokih, Saveliy Skresanov
(Novosibirsk State University).
Let F be the function F(x) ¼ x2 −2. It is obvious that F is an inverse function,
n

since for the given element it puts into correspondence the multiplicative
inverse element in GF(2n). The classic result related to our problem can be
found in Nyberg (1994). It is proven there that the nonlinearity of this func-
tion has the following lower bound: nlF ≥ 2n−1 − 2n/2. The answer is positive
since all of the conditions are fulfilled.

5.12. Problem “Covering radius — 2”

Solution. Denote by L the linear subspace spanned by the given vectors.
First, we notice that permutation of coordinates in Fn2 is an isometry and
therefore does not change the maximum distance and metric complement
in any irreversible way. A permutation of coordinates corresponds to a
permutation of columns in the given matrix. We permute the columns of
the matrix so that we get
0 1
1 0 0 ��� 0 0 j 1 1 0 0 ��� 0
B0 1 0 ��� 0 0 j 0 1 1 0 ��� 0C
B C
B0 0 1 ��� 0 0 j 0 0 1 1 ��� 0C
B C
M¼B .. .. .. C
B . j . . C
B C
@0 ��� ��� ��� 1 0 j 0 0 0 ��� 1 1A
0 ��� ��� ��� 0 1 j 1 0 0 ��� 0 1
which is easier to work with. Both halves have k columns.
Then, note that if d(y, L) ¼ k, then for any x 2 L the distance from y � x to
L is also k because
dðy � x; LÞ ¼ min dðy � x; zÞ ¼ min dðy; x � zÞ ¼ min dðy; zÞ ¼ dðy; LÞ:
z2X z2X z2X

Thus, the metric complement of L is the union of sets of the form y � L-

¼ {y � x: x 2 L}, and we only need to find one vector from each set to
describe the complement.
 CRYPTOLOGIA 23

From an arbitrary y � L, we can take (uniquely) the vector z such that it has
zeros in the first k coordinates, because the first k columns of the matrix M0
form a nonsingular square matrix. Moreover, the arbitrary vector z with zeros
in the first k coordinates lies in z � L. We can limit our search from Fn2 to
L� ¼ fz 2 Fn2 : z1 ¼ z2 ¼ � � � ¼ zk ¼ 0g.
Let y be a vector from Fn2 . We can express it as y ¼ (y1|y2), where
y1 ; y2 2 Fk2 . Then, all vectors from L* are of the form z ¼ (0|z2). Consider
the following procedure (P*)
1. s: ¼ 1, K ¼ h;
2. If the s-th and (s + 1)-th coordinates of z2 are both 1, then z : ¼ z � es, add s
and s + 1 to K (if s ¼ k then (s + 1) → 1);
3. s : ¼ s + 1;
4. If s is greater than k, then STOP; otherwise, go to step 2.
Applying this to any vector z 2 L* we get some vector a ¼ z � x, x 2 L.
Obviously, a2 has no consecutive 1s, because what the algorithm does is
eliminate them (here a2 is viewed as a cyclic vector). Assume that l basis vec-
tors were added to z during the procedure. Then, wt(a1) ¼ l.
Consider the vector a�2 of length k − 2l obtained from a2 by deleting coor-
dinates that are in the set K (a2 has zeros in these coordinates). If there are two
consecutive 1s in the vector a�2 , (here a�2 is not viewed as a cyclic vector), then
they were either consecutive in vector a2, or they were not. The first is imposs-
ible, as has already been mentioned earlier. The second means that in the vec-
tor a2 there is 1 in position s that precedes position (s + 1) from the set K. This
is also impossible, because in this case the algorithm would have eliminated
the 1 in position s first. There are no consecutive 1s in the vector a�2 , and
therefore not more than dk 22le ones in the vector a�2 (and also in a2). There-
fore, the weight of a is not greater than dk 22le þ l ¼ dk2e. In other words,
� �
k
dðLÞ � dðz; LÞ � dðz; xÞ ¼ wtðaÞ �
2
Now let us show that this is the exact value. Let z* ¼ (0|1). Addition of
any basis vector adds one 1 to the first half of z* and removes not more than
two from the second. Therefore, for any x from L we have d(x, z*) ¼ wt(x �
z*) ≥ wt(z*) + l − 2l ¼ k − l, where l is the number of basis vectors in the
decomposition of x. If l is not greater than bk2c, then through the obtained
inequality we get that dðx; z� Þ � dk2e. If l is not less than dk2e, then the weight
of the first half of x � z* alone is not less than d2ke, and d(x, z*) is also not
less than that. For any x 2 L, we have dðx; z� Þ � d2ke, which proves that d(L)
is equal to d2ke.
If k is odd, then this is the only vector from L* that is in the metric
complement. Let z be any other vector from L*. Permute the last k coordinates
cyclically so that the last coordinate of z is zero (the second half of the matrix
24 S. AGIEVICH ET AL.

stays the same until the permutation of the rows). After applying (P*), we get the
vector a such that wt(a1) ¼ l and wtða2 Þ � bk 22lc, because a�2 is of odd length,
has zero at the end, and has no two consecutive 1s. So dðz; LÞ � wtðaÞ � b2kc.
Let k be even, z 2 L*, z ≠ z*. Let z2 (as a cyclic vector) have a group of con-
secutive 1s of even size 2j. We can add j basis vectors to z so that this group is
eliminated, getting the vector a. Now we have a group of at least 2j + 2 zeros
in a2 (to the left and right from that group of 1s, there were zeros, too).
Excluding this group from a2 and applying (P*) to the resulting (this time
not cyclic) vector a02 of length k − 2j − 2, we add l basis vectors, and the result-
ing b2 has not more than k 2j 2 2 2l ¼ 2k j l 1 ones, because b�2 cannot
have more than two consecutive 1s (it can have two because of that removed
coordinates breaking cyclicity). If we put everything together, the resulting
vector has weight not greater than j þ l þ 2k j l 1 ¼ 2k 1. So, z can
not be in the metric complement.
This argument can be applied to vectors z so that z2 has two consecutive
zeros by assuming there is a group of 0 ones between those two zeros.
Now let us assume that the second half of z 2 L* does not have two con-
secutive zeros and all groups of consecutive ones are of odd size. Let x 2 L
be the closest vector to z. If the decomposition of x has two consecutive basis
vectors, then they add 2 to the weight of (z � x)1 and subtract no more than 2
from the weight of (z � x)2, so we can remove them. So without loss of
generality the decomposition of x does not have two consecutive basis vectors.
Due to this, if the s-th and (s + 1)-th coordinates of z2 are (01), (00), or (10),
then es is also not in x, because it would only add to the distance. With that in
mind, every group of ones (of odd size) is independent from others in the
sense that if es is in x, then all two 1s of the second half of es are in the same
group. Every group of size 2j − 1 contributes exactly j to the distance (as
proved for z*), and has one zero after it, so the vector z2 can be split in groups
of even size 2j of the form (111…0), each adding j to the distance. Thus, the
distance from x to z is equal to 2k.
All in all, d(X) is equal to d2ke, the metric complement consists of
– z* � L, whereSz* ¼ (0|1), if k is odd;
– z* � L and z � L, where Lodd is the set of vectors from L* such that
z2Lodd
their second half does not have two consecutive zeros, and all groups of
consecutive ones are of odd size, if k is even.

5.13. Problem “An elliptic curve”

Solution. The best solution was sent by participant Renzhang Liu (Beijing,
Academy of Mathematics and Systems Science).
If (a, b) is an integer point on the curve y2 ¼ x3 + 56x ¼ 6, and p is a prime
factor of b, then (x − a)2 is a factor of x3 + 56x + 6 ¼ 0 over Fp. Then, g(x)
 CRYPTOLOGIA 25

and g0 (x) has a common factor x − a over Fp, where g(x) ¼ x3 + 56x + 6 and g0
(x) ¼ 3x2 + 56. Since 3g(x) − xg0 (x) ¼ 2(56x + 9), we know that x − a is also a
factor of 2(56x + 9).
Note that p must be odd, since for any b 2 2Z, b2 mod 4 ¼ 0, and a3 + 56a
+ 6 mod 4 ¼ a3 + 2 mod 4 will never be 0. Then, a3 + 56a + 6 ¼ 1 mod 8,
which gives a mod 8 ¼ 3. Similarly, we know that p ≠ 3; 7. Polynomials x − a
and 2(56x + 9) are of the same degree, we know a ¼ −9·(56)−1 mod p.
Note that g0 (a) ¼ 0. Then we have 3·81 + 563 ¼ 0 mod p, which is
175859 ¼ 0 mod p. Since 175859 is a prime, we know that p ¼ 175859.
However, x3 + 56x + 6 ¼ 0 mod p has no solution over Fp, which means that
there are no integer points on the curve y2 ¼ x3 + 56x + 6.
Many participants obtained partial results. The majority of them used
modular arithmetic and tried to find restrictions on possible values of
variables.

5.14. Problem “The machine D H d ”

Solution. The following solution was proposed by Anna Gusakova, Dzmitry
Emelyanov, and Vadzim Marchuk (Belarusian State University). It is very
short, but it requires quite a big number of queries to D H d .
Let us define the polynomial fd−1(x) ¼ (x + 1)d − (x − 1)d over Zq, then
1
1Þd
¼ DHdðg; gg x ÞðDHdðg; g 1 g x ÞÞ 1 :
d
gf d 1 ðxÞ ¼ g ðxþ1Þ ðg ðx Þ
Denote by DHd−1 the machine that calculates gfd−1(x) by g and gx.
Next, we can define fd−2(x) ¼ fd−1(x + 1) − fd−1(x − 1) and the machine DHd
−2 that calculates
,
1Þ 1 1
gf d 2 ðxÞ ¼ gf d 1 ðxþ1Þ ðg f d 1 ðx Þ ¼ DH d 1 ðg; gg x ÞDH d 1 ðg; g 1 g x ÞÞ
and so on.
The degree of the polynomial fk(x) is equal to k. In fact, the eldest
coefficient e is equal to 2d·2(d − 1)·…·2(k + 1), as long as d is small and q is
a large prime number. It holds that (e, q) ¼ 1.
Therefore, we have constructed the machine DH2, which calculates
2
gax +bx + c, a, b, c 2 Zq, a ≠ 0. Let us construct D H 2 in the following way:
2 2 1 1 1
g x ¼ ðg ax þbxþc Þa � ðg x Þ ba
�g ca
:
Next, we can get
1
g xy ¼ ðDH2ðg; g x g y Þ � ðDH2ðg; g x ðg y Þ 1 ÞÞ 1 Þ4 :
Thus, the total number of queries to D H d is equal to 2d−1.
The solution with the minimal query number was proposed by Alexey
Udovenko (University of Luxembourg). Other complete solutions were
26 S. AGIEVICH ET AL.

proposed by Alexey Miloserdov, Nikita Odinokih, Saveliy Skresanov (Novosi-

birsk State University); Roman Ginyatullin, Victoriya Vlasova, Igor Motroni
(Moscow Engineering Physics Institute); Konstantin Kogos, Sergey Kyazhin,
Anna Epishkina (Moscow Engineering Physics Institute).

5.15. Problem “Palindrome cipher”

Solution. First, we find the key used to encrypt the congratulation.
Because the bits of the key are ASCII codes of digits, we may suppose that the
key is a 16-digit number. We have 1016 variants of the keys, and this number is
too large to implement an exhaustive search. Using a meet-in-the-middle attack,
we can reduce the complexity of the exhaustive search to 109 operations. This
can be implemented quickly on a PC:
1. Encrypt the plaintext with the DES cipher using each variant of the DES-
key one by one to get all 108 possible intermediate ciphertexts.
2. Decrypt each ciphertext by the Blowfish algorithm using each possible
Blowfish-key one by one to get all 108 possible intermediate ciphertexts.
3. The intermediate ciphertexts are the original plaintexts after applying DES
to them, but before applying Blowfish. Consider the intersection of these
two sets of intermediate ciphertexts and mark out all the variants of used
DES and Blowfish keys.
4. Steps 1 to 3 can be applied to each block (8 bytes) independently, because
the ECB format of encryption was used. Apply these steps to each block to
ensure that the obtained keys do encrypt each block correctly.
Using the program, we can find all possible variants of the key, encrypting
the given congratulation into a fixed ciphertext. Note that 256 variants of the
DES-key and one variant of the Blowfish-key are obtained.
One possible variant of the key is 0 6 0 6 2 0 0 2 2 2 9 3 5 1 6 2 .
DES uses only 7 bits of each byte of the key (the eighth was considered as
being the parity check bit and is not used in this case). It explains all 256
variants of the DES-key. They all differ only in the least significant bits of each
byte.
We can derive from the statement of the problem that in 2005, the com-
pany was 12 years old, so it was founded in 1993. Hence, the twentieth anni-
versary of the company was in 2013. It is likely that the first part of the key is
the date in D D MMY Y Y Y format. Then, the date of the twentieth anniversary is
one of 06, 07, 16, 17 days in June (06) or July (07) (it is uncertain because of
the parity check bits of the DES key).
Remember that company is named Palindrome. Consider the variant of the
key 0 6 0 6 2 0 1 3 2 2 9 3 5 1 6 2 . It is not a palindrome, but is very close to one.
In a random date D0D1M0M1Y0Y1Y2Y3, there was a key D0D1M0M1Y0
Y1Y2Y3abcdefgh, where a ¼ Y3 − 1, b ¼ Y2 + 1, c ¼ Y1 − 1, d ¼ Y0 + 1, e ¼ M1 −
1, f ¼ M0 + 1, g ¼ D1 − 1, h ¼ D0 + 1 modulo 10. We can decrypt the main
 CRYPTOLOGIA 27

ciphertext by trying out the dates in inverse order from the date of the
Olympiad start 16.11.2015.
The key 0 1 1 1 2 0 1 5 4 2 9 3 0 2 0 1 decrypts the ciphertext as:
Q u o t e o f t h e d a y : �Mo s t p e o p l e s a y t h a t i t i s t h e
i n t e l l e c t wh i c h ma k e s a g r e a t s c i e n t i s t . T h e y a r e
wr o n g : i t i s c h a r a c t e r . A l b e r t E i n s t e i n �

5.16. Problem “Hypothesis” (unsolved. special prize)

Solution. This problem is based on the hypothesis (1966) of G. P. Agibalov.
The statement of this conjecture is the following:
Hypothesis. For all n ≥ 2, there exists a Boolean function g : Fn2 1 ! F2 in
the disjunctive normal form, where every variable appears not more than one
time, so that a binary sequence {u1, u2, …} produced for all t ≥ 1 from the
initial state u1,…, un according to the following rule
utþn ¼ ut � gðutþ1 ; utþ2 ; � � � ; utþn 1 Þ
has the maximal possible period equal to 2n.
This hypothesis had been partially proved for every n ≤ 22 in Agibalov
(2007).
There was no complete solution of the problem. The best attempt was pro-
posed by Mikhail Borodin, Katerina Karelina, and Lyudmila Kushchinskaya
(Lomonosov Moscow State University). Their solution was based on linear
recurrent sequences, but contained an unremovable mistake.

5.17. Problem “A secret sharing” (unsolved. special prize)

Solution. There was no complete solution of this problem, either. The most
popular ideas of the participants were implemented in the algorithm to
generate the set M and in the analysis of small dimensions. Interesting
attempts were proposed by the teams of George Beloshapko, Anna
Taranenko, and Evarist Fomenko (Novosibirsk State University, Sobolev
Institute of Mathematics); Roman Ginyatullin, Victoriya Vlasova, and Igor
Motroni (Moscow Engineering Physics Institute); Ivan Emeliyanenkov
(Novosibirsk State University); Sergei Titov, Roman Taskin, Prokhor Sadkov,
and Konstantin Kirienko (Ural State University of Railway Transport).

6. Winners of the Olympiad

In this section, we provide information about the winners of
NSUCRYPTO’2015.
28 S. AGIEVICH ET AL.

Winners of the first round in the school section A (“senior pupils”)

Place Name Country, City School Grade Score

1 Vladimir Schavelev Russia, Novosibirsk Gymnasium 6 9 20
2 Ekaterina Bestsennaya Russia, Novosibirsk SESC NSU 11 19
2 Alexey Solovev Russia, Moscow AESC MSU 10 19
3 Alexander Dorokhin Russia, Novosibirsk MOU 159 9 18
3 Arkadij Pokazan’ev Russia, Novosibirsk Gymnasium 6 8 17
3 Ivan Lozinskiy Russia, Moscow AESC MSU 11 17
3 Ivan Sutormin Russia, Novosibirsk SESC NSU 11 17
3 Alexandr Evpak Russia, Novosibirsk SESC NSU 11 16
Diploma Nikita Mingaleev Russia, Novosibirsk SESC NSU 11 15
Diploma Ivan Baksheev Russia, Novosibirsk Gymnasium 6 8 15

Winners of the first round in student section B (in the category

“students”)

Place Name Country, City University Department Year Score

1 Peter Russia, Saratov State Computer Science 5 14
Razumovsky Saratov University and Information
Technology
2 Evgeniy Russia, Saratov State Computer Science 5 13
Strepetov Saratov University and Information
Technology
2 Nikita Russia, Novosibirsk State Mathematics and 4 13
Odinokih Novosibirsk University Mechanics
2 Sergey Russia, Saratov State Computer Science 4 13
Zhdanov Saratov University and Information
Technology
3 Alexey Russia, Novosibirsk State Mathematics and 3 12
Miloserdov Novosibirsk University Mechanics
3 Aliaksei Belarus, Belarusian State Faculty of Applied 5 12
Ivanin Minsk University Mathematics and
Computer Science
3 Pavel Hvoryh Russia, Omsk State Information 4 12
Omsk Technical University Technologies and
Computer Systems
3 Elena Russia, Novosibirsk State Economics 2 12
Khabarova Novosibirsk University
3 Mikhail Kotov Russia, Tomsk State Applied Mathematics 3 12
Tomsk University and Cybernetics
3 Vitaliy Russia, Novosibirsk State Mathematics and 2 12
Cherkashin Novosibirsk University Mechanics
 CRYPTOLOGIA 29

Place Name Country, City University Department Year Score

Diploma Vladimir Russia, Omsk Omsk State Radio 3 12
Laptev Technical Engineering
University Faculty
Diploma Anastasiya Russia, Engels Saratov State Computer Science 3 12
Yarunina University and
Information
Technology
Diploma Charles de Russia, Novosibirsk State Mathematics and 5 10
Mauroy Novosibirsk University Mechanics
Diploma Jakub Klemsa Czech Republic, Czech Technical Mathematics 5 10
Prague University in
Prague
Diploma Alexey Russia, Saratov Saratov State Computer Science 4 10
Ripinen University and
Information
Technology
Diploma Anastasia Russia, Moscow Lomonosov Computational 4 10
Kislyakova Moscow State Mathematics
University and
Cybernetics
Diploma Roman Russia, Novosibirsk State Physics 3 10
Lebedev Novosibirsk University
Diploma Oleg Smirnov Russia, Saratov Saratov State Computer Science 5 10
University and
Information
Technology
Diploma Konstantin Belarus, Minsk Belarusian State Applied 5 9
Pavlov University Mathematics
and Computer
Science

Winners of the first round in the student section B (in the category
“professionals”)

Place Name Country, City Organization Score

1 Renzhang Liu China, Beijing Academy of Mathematics and 27
Systems Science
2 Vadzim Marchuk Belarus, Minsk Belarusian State University, Research 25
Institute for Applied Problems of
Mathematics and Informatics
3 Alexey Udovenko Luxembourg, University of Luxembourg 17
Luxembourg
Diploma George Russia, Novosibirsk Novosibirsk State University 14
Beloshapko
Diploma Andrew Kozlik Czech Republic, SII 12
Prague
30 S. AGIEVICH ET AL.

Winners of the second round (in the category “senior pupils”)

Place Name Country, City School Grade Score

Diploma Ivan Lozinskiy, Bogdan Russia, Moscow AESC MSU 11 11
Sinitsyn, Maxim Plushkin
Diploma Andrei Igo Russia, Novosibirsk Gymnasium 6 10 6

Winners of the second round (in the category “students”)

Place Name Country, City University Department Year Score

1 Alexey Russia, Novosibirsk State Mechanics and 3 41
Miloserdov, Novosibirsk University Mathematics
Nikita
Odinokih,
Saveliy
Skresanov
2 Alexey Ripinen, Russia, Saratov State Computer Science and 5 34
Oleg Smirnov, Saratov University Information Technology
Peter
Razumovsky
3 Roman Russia, Moscow IB, Cybernetics and 4 31
Ginyatullin, Moscow Engineering Information Security,
Victoriya Physics Institute Information Security of
Vlasova, Igor Automated Systems
Motroni
Diploma Irina Slonkina Russia, Novosibirsk State Information and 3 18
Novosibirsk University of Technologies
Economics and
Management
Diploma Samir Godzhaev, Russia, Lomonosov Mechanics and 2 17
Ravil Khisamov Moscow Moscow State Mathematics
University
Diploma Roman Russia, Moscow Cybernetics and 4 16
Rezvukhin, Moscow Engineering Information Security
Vladimir Physics Institute
Martyshin,
Mikhail
Zaytsev
Diploma Roman Taskin, Russia, Ural State Information 3 14
Prokhor Yekaterinburg University of security
Sadkov Railway
Transport
 CRYPTOLOGIA 31

Winners of the second round (in the category “professional”)

Place Name Country, City Organization Score

1 Alexey Udovenko Luxembourg, University of Luxembourg 48
Luxembourg
2 George Beloshapko, Anna Russia, Novosibirsk Novosibirsk State University, 42
Taranenko, Evarist Institute of Mathematics
Fomenko
3 Anna Gusakova, Dzmitry Belarus, Minsk Belarusian State University, 30
Emelyanov, Research Institute for
Vadzim Marchuk Applied problems of
Mathematics and Informatics
Diploma Mikhail Borodin, Katerina Russia, Moscow Lomonosov Moscow State 28
Karelina, Lyudmila University
Kushchinskaya
Diploma Konstantin Kogos, Russia, Moscow Moscow Engineering 27
Sergey Kyazhin, Physics Institute
Anna Epishkina
Diploma Evgeniya Ishchukova, Russia, Taganrog Southern Federal 26
Ekaterina Maro University
Diploma Sergey Belov, Russia, Obninsk, Lomonosov Moscow State 23
Grigory Sedov Moscow University
Diploma Jakub Klemsa, Tomas Czech Republic, Czech Technical 22
Jeziorsky, Andrew Kozlik Prague University in Prague

About the authors

S. Agievich is the head of the IT Security Research Laboratory of the Research Institute for
Applied Problems of Mathematics and Informatics (Belarusian State University). He teaches
the “Cryptographic methods” course in the Faculty of Applied Mathematics and Informatics.
His research interests: Boolean functions in cryptography, cryptographic algorithms and
protocols, enumerative and asymptotic combinatorics, exponential sums and systems of
polynomial equaitions.
A. Gorodilova is a researcher at the Laboratory of Discrete Analysis in the Sobolev Institute
of Mathematics; she teaches courses in Boolean functions and cryptology at Novosibirsk State
University and Specialized Educational Scientific Center of Novosibirsk State University. She
is interested in cryptographic Boolean functions, APN functions, bent functions, symmetric
cryptography, combinatorics, and algebra.
V. Idrisova is a PhD student in the Sobolev Institute of Mathematics. Also, she teaches a
course in cryptology and information theory for master students at Novosibirsk State
University. Her research interests includes vectorial Boolean functions, block ciphers, and
side-channel attacks.
N. Kolomeec is a researcher at the Laboratory of Discrete Analysis in the Sobolev Institute
of Mathematics. He teaches courses in cryptology in the Department of Mathematics and
Mechanics at Novosibirsk State University. His research interests are Boolean functions in
cryptography and pseudorandom sequences.
G. Shushuev is a PhD student at the Laboratory of Discrete Analysis in the Sobolev Institute
of Mathematics; he teaches special course in cryptology in the Department of Mathematics and
Mechanics at Novosibirsk State University. His research interests include block and stream
ciphers, cryptanalysis, and cryptographic protocols.
N. Tokareva is a senior researcher at the Laboratory of Discrete Analysis in the Sobolev
Institute of Mathematics; she teaches courses in cryptology in the Department of Mathematics
32 S. AGIEVICH ET AL.

and Mechanics at Novosibirsk State University. Her research interests include Boolean func-
tions in cryptography, bent functions, block and stream ciphers, cryptanalysis, coding theory,
combinatorics, and algebra.

Acknowledgments
We are very grateful to Gennadiy Agibalov, Svetla Nikova, Irina Pankratova, Bart Preneel,
and Vincent Rijmen for their valuable contribution to this article: ideas for the problems
and all-out support. We thank Alexey Oblaukhov for his kind help during the Olympiad
and in the process of writing this article. We thank Novosibirsk State University for the
financial support of the Olympiad and invite you to take part in NSUCRYPTO-2017 that starts
on 22 October 2017. Your ideas on the unsolved problems are also very welcome and can be
sent to [email protected].

Funding
The article was financially supported by RFBR (grants 15-07-01328, 15-31-20635), by the Min-
istry of Education and Science of the Russian Federation and grant N 0314-2015-0011.

References
Agibalov, G. 2007. Normal reccurent sequences, Bulletin of Tomsk State University.
Supplement. 23:4–11 (in Russian).
Agievich, S., Gorodilova, A., Kolomeec, N., Nikova, S., Preneel, B., Rijmen, V., Shushuev, G.,
Tokareva, N., Vitkup, V. 2015. Problems, solutions and experience of the First International
Students’ Olympiad in Cryptography. Applied Discrete Mathematics (Prikl. Diskret.
Matemat.). 3:41–62.
Bell, C. 2013. The internet mystery that has the world baffled. The Telegraph, 25 November,
www.telegraph.co.uk/technology/internet/10468112/The-internet-mystery-that-has-the-world-
baffled.html.
Bogdanov, A., Knudsen, L. R., Leander, G., Paar, C., Poschmann, A., Robshaw, M. J. B., Seurin,
Y., Vikkelsoe, C. 2007. PRESENT: An ultra-lightweight block cipher. In Cryptographic
Hardware and Embedded Systems — CHES. LNCS 4727:450–466. Berlin: Springer.
Burton, B. A. 2008. Breaking the routine: Events to complement Informatics Olympiad training.
Olympiads in Informatics. 2:5–15.
Diffie, W., Hellman, M. E. 1976. New Directions in Cryptography. IEEE Transactions on
Information Theory, IT-22(6):644–654.
National Bureau of Standards. 1977. Data Encryption Standard. FIPS publication, N. 46, U. S.
Department of Commerce.
Nyberg, K. 1994. Differentially uniform mappings for cryptography. In Advances in Cryptology
– EUROCRYPT’93 LNCS 765:55–64. Berlin: Springer.
Schneier, B. 1994. Description of a new variable-length key, 64-bit block cipher (Blowfish).
Fast Software Encryption, LNCS 809:191–204. Berlin: Springer.