Universal (Hexa)Decimal Classification

Since I have started with research over elliptic curves, many papers, book and other similar stuff has been read by me to take the knowledge. But there is an issue when the number of this things get too big. How can I organize the information of those papers (or books and so) in order to get back to this information and refresh the memory contents?

Very long a go, I did a course on bibliographic search and catalogue. In this course I have learned the way that the libraries in general organizes the books in there: the UDC (Universal Decimal Classification). I've looking how can I reuse this to classify the documents I think relevant for my research.

I have set up my own main classes and also I have tried to let at least one of them vacant for further updates, that mean to extend the fields of research. Event that pretension, by today, it's full again. This means that probably I'll have to do my second refactoring of this structure, because in the past I had once already this problem.

There is another way to modify my classification to have more vacants, that is think in another base. As far as I understood, the UDC was restricted from 0 to 9 to have like only one character field. Then why not a computer scientist can think in a Universal Hexadecimal Classification (UHC)?

For the records, my current main classes and their categories:

• 0.Mathematics
• 010.Number Theory
• 020.Abstract Algebra
• 030.Information Theory
• 040.Logic
• 050.Elliptic curves
• 1.Public Key
• 101.Finite fields cryptography
• 102.Elliptic curves cryptography
• 103.Hyperelliptic curves cryptography
• 110.Cryptoanalysis
• 111.Finite fields cryptoanalysis
• 112.Elliptic curves cryptoanalysis
• 113.Hyperelliptic curves cryptoanalysis
• 120.Isogenies
• 121.Isogeny volcanoes and stars
• 122.Isogenies cryptography
• 2.Symmetric cryptology
• 210.Rijndael
• 3.Hash functions
• 310.SHA
• 320.Elliptic and hyperelliptic curves
• 4.Stream cyphers
• 5.Secret sharing
• 6.Homomorphic encryption
• 7. vacant
• 8. vacant
• 9. vacant
• A. vacant
• B. vacant
• C. vacant
• D.Computation
• D10. Distributed systems
• D20. Parallel computing
• E.Hardware
• E10.Embedded systems
• E20.Smartcards
• E30.Rfid
• F.Standards
• F01.Internationals
• F10.European
• F20.North American
• F30.Russian

Because to the uncategorised classes, I think this is full and it's the first place to start merging classes and dividing them in categories. The solution of the hexadecimal, even if I have already applied, is not fixed for ever. May some day, certain categories would be subcategories. Currently this classification contains 409 documents (papers, books, and so on). My bibtex files aren't and they should.

What this system is not complaining is how to archive the notes that I wrote in the margins on the papers I read and place in here or the marks I set labelling pages on books, and so on. But this is an issue that this tool is not useful for.

How to have a search tool on this structure and inside those documents, including the posted comments?

(more) frustraited @ work

Alba is broken like since eastern. When we come back from that shutdown at the end of March. Water cooling problems, the water flow was unstable; sponges were found in the "clean water" cooling pipes, together with other dust; a weekend instrument hang causes a temperature increase and bad quality of hoses become vulcanized (below the specs) and caused a disaster in one of the two main power supplies of the booster; a TLD wrong placed in a weird space and when an Insertion Device was moved, it bends the beam pipe blocking the beam orbit, requiring to vent and replace a section. It's like we stomp shit.

This is one of the issues in this accelerator complex, but there are others that may interact.

Panic reaches the management at the beginning of this years when 12 people announces their new positions in other institutes. If you take into account that we are 145 workers, you can realizes the magnitude of the problem. From the people that says goodbye, 8 were from the computing division (around 50) and from those 4 were from the controls section (of 14). This panic didn't mention the 1 or 2 per month that has announced that the left during the past two years.

Management has announced 3 months later the creation of a commission from work behaviour improvements. Now, in July, this commission has made the first meeting by last week.

As I mention in the previous post, another reason of personal sadness: my bosses didn't case about a worker that has been called to do a talk in the university.

I didn't write here since then. I didn't found any reason to write about software design here.

But last reason to get one step further in frustration went last week.

Starting 2 months a go, in the tango meeting, there was a request to the tango community to introduce security embedded inside the tango implementation. From the last 4 years I've been trying to start a PhD in cryptology (but too busy due to the work at Alba), and I've been getting closer and closer to the field of the RFIDs and the smartcards. During the presentation where this was requested, I thought that many of the schemas to ensure RFID can be also valid to be applied in between the communication of the agents in a distributed system, like tango.

I thought it can be interesting for Alba and the tango community, to exploit that one of the workers has a hobby in cryptology and security. In this terms I've talked to my boss.

For that, I need 3 weeks to talk to my boss (this is already one problem). During this time, I've been able to, out side working hours, explain this idea to the research group in the university (they are in another city, 150 km away). I found a great acceptance about "Ensuring Tango control system", even more I've seen enthusiasm about the idea of a PhD based on an application of all the cryptological work made by the whole group (many things about public key -specially elliptic curves- symmetric cyphers, stream ciphers, secret sharing, homomorphic encryption and field like that).

At work, the response wasn't that good. The answer was like: "do what ever you like in your free time, but this must not affect your current duties at all. It's not possible to dedicate any of your working hours in such a thing". Clearly have said, if I do a PhD, is not meaning anything for Alba at all. Ooh!! This is a very clear way to motivate a worker. For my partners, also fun when was said "if you do, others would ask to do this", what's the problem on workers training?

Went I talked to my boss, I said many time to him and have to point here, that my duties have been increase every time that a partner left. Last Friday, there was a presentation about the Alba's controls system, and when the subsystems of the machine was listed, half of the elements on that list are on my behalf (and not all my duties were there).

When I went to talk about this with my boss, I went there offering my free time to work in a industrial PhD. My proposal was not to stop doing my job and disappear for full time dedication to this, my proposal was mostly the free time, but being realistic that the brain thinks at any time. As a collaboration between the university and the industry, all the involved has to put something, specially the PhD candidate.

Well done, with this deal, the simpler solution is that Alba will not appear at all in my PhD. Or if it appears will be to be mention explicitly that they haven't contribute at all; even worst Alba's position was opposition to doing a work like that.

Generalized Rijndael, schematics

Before to enter in deep on the questions remarked in the previous post about this series, I like to post some schemas that some day would be useful.

The Rijndael symmetric cryptosystem build by iteration using a network of permutations who follows the basic shannon's properties of "confusion and diffusion". The bits in the plain text are mixes and substituted by a group of operations do by an order. To decrypt, what have to be done is to do the same things but in the opposite way. For sure, there is a key to introduce here the secret to be able to undo the encrypt operation.

Diagram 1: Flow of the Rindael encrypt/decrypt

As in the diagram 1 shows, using only 4 operations (subBytes, shitfRows, mixcolumns, addRoundKey, and its inverses). But those operations are in a certain order to maintain a set of properties.

• subBytes: word substitution, where each element in the state matrix is replaced by its inverse and an affine mapping. Operations in
• shiftRows: cyclic left shift of the elements of the i'th row by i words.
• mixColumns: column linear transformation of the state matrix, where each column is given as an element of a polynomial ring, where the coefficients of this polynomial are polynomials in .
  This polynomial ring is: 
• addRoundKey: XORed transformation between the state matrix and the round key.

Is necessary to emphasize the use of a part of the key in the 'addRoundKey()' operation. This round key is much longer than the given key to encrypt/decrypt, and the process to generate this key expansion can be described in a iterative way:

Diagram 2: Iterator schema of the Rijndael key expansion

The first 4x4 matrix (the ) is the original key given with in a structure of a matrix of elements in the wordsize (8 bits, a byte in rijndael, AES). This example is using the 128 key option but the key matrix can have more columns: To build the key expansion its the same way, but remark that "#c" represents the number of columns for the message, not the key.

To build the following columns to have each round keys, an iterator is good to see how this is made. I have tried to get an schema from other webs sites, but the ones that I found haven't convinced to me. I hope this would help to someone who search on internet for a diagram of the rijndael key expansion.

RFC 6637 and construct elliptic curves

A new request for comments is available for elliptic curve cryptography. With the number 6637 the past June 11th was announced as official. Very good news for the elliptic curves and its cryptographic implementations. 


From the first version of this standard when it was a candidate has passed a few months more than 4 years. Yes, more than 4 years to public discussion. Necessary for consensus in standard development, but much more necessary for cryptography.


The old project of the patch for GnuPG, who was already obsolete a long a go, have some relation with the final code in the GnuPG. I'm glad when I see it in the sources that I have contributed somehow.


But what about the supported curves? The mentioned standard restricts the use of only a very few of them. The supported curves are only 3, one per each supported size: from the fips 186-3 the p-256, p-384 and p-521 (the biggest 3 of the 5 in the Appendix D.1.2 "Curves over Prime Fields). They are known as the NIST curves and they are from the NSA suite b.


Yes, the standard doesn't close completely the use of other curves. There is a field in the structure of the key to specify the curve, but is not set directly the curve. What is place in the field is the curve OID. Even if the number of curves that can be listed using this Object Identifiers can be very big, it will never be as big as the existing and cryptographically valid elliptic curves. But there is hope in this issue, it wasn't like that the full time of this pre-standard process, there is a octet, the first one, who have a reserved value (0xFF) for future extensions.


Why can be so important to use as many curves as the users want? Easy, one of the biggest features in elliptic curves is the possibility to change the cyclic group where the discrete logarithm is protecting your secrets, without changing the size is because using a different curve with in the same base finite field the hardness of move an attack from the cyclic group in one curve to another cyclic group in another will be almost equivalent to start from scratch the attack over the new cyclic group on the new curve over the same finite field.


But, how can be a new curve generated? Recently in arxiv I've seen a article about this matter: "Method for constructing elliptic curves using complex multiplication and its optimizations" (July 30, 2012).


I've been working in isogenies using volcanoes and stars of them to speed up the initial way to construct a new curve (pointed in the abstract of the cited article):

1. 
2. , where and
3. If it doesn't satisfy the conditions restart from 1

But this article proposes the other way around, start finding an order that satisfy the conditions and then build a curve of this order. It's a promising idea to have a nice way to have as many curves as necessary. 


With the isogenies, I didn't found how to speed this up enough to have a new (cryptographically good) curve during the key generation (a reasonable time to not desperate the user). And even more, having the possibility to reset your key by change and old curve by a new one with out needing to create a new key, but assuring the security by a public and auditable procedure.

What is the utility of this feature of the cryptosystem reset? One that I can imagine, and can be compatible with the current standard is to have a corporative elliptic curve in the smart cards and periodically renew the curve. Knowing the path in the isogeny star, all the smart cards would be able to "migrate", but for a cryptoanalyser will be a very enormous hard work to "port" any running attack, even if the public keys are available in both curves, from the origin to the current if the path is still secret.

The most important thing in cryptology is the trust on mathematics. Giving the user 3 curves, that looks good, but only 3, is not enough. Like the S-boxes in DES, that wakes up susceptibilities, specially at the beginning, to know how they had been build (why those and not any other). Even more, giving a list of hundreds of thousands curves is neither enough because the problem is still the same.

The unique solution I see on that issue, is to give this public and auditable algorithm that allows the community to validate (or break) it that make the user confortable with the provided security.

Generalized Rijndael, a review

After a too long period of time with out working on this project I like to recover it.

I did a python implementation, that will be publish as free software (GPL) who is able to change the usual parameters of the Rijndael to work in a very different way than the 3 options of the standard. As a review:

Rijndael variable parameters:

• Number of rounds
• Number of rows
• Number of columns
• Wordsize (in bits)
• Number of columns in the key

The 3 standard sizes are: {10,4,4,8,4}, {12,4,4,8,6}, {14,4,4,8,8} and this means:

• Block size always 4x4 elements of 8 bits 128 bits
• Key size can have 4, 6 or 8 columns 128,192,256 bits
• And depending on this key size the number of rounds varies from 10, 12 or 14.

But this can be changed easily by something like: {40,2,2,8,8} and this means a Rijndael of 32 bits block with keys of 128 bits (doing 40 rounds, but this was set like this in the experiment because other small block ciphers have values like this).

But what means internally to the algorithm this change?

• A new irreducible polynomial is need for the mixColumn() transformation, because the polynomial ring have the same number of coefficients than the number of rows.

Are there other options in Rijndael to get this combination? Yes: this would be equivalent to {40,4,4,2,16} and what does this mean?

• A new Rijndael SBox must be build: the original is made to apply a substitution of works of 8 bits.

Pending demonstrations:

• Is the generalized Rijndael still a Pseudo-Random Permutation (PRP)
• How to build secure SBoxes?
• How to get irreducible polynomials to be able to change the number of rows?
• Is the invertible circulant matrix also valid for polynomial rings over , with ?
• How to calculate the number of rounds necessary? Not less than need to be insecure, but not more to do superfluous calculations.

Generalized Rijndael, an approach

Following the idea of the first post about a Generalized Rijndael, I have started an implementation with some constants of the standard implementations becomes variables.

An schematic for the Rijndael would be:

This operations uses a state matrix, it's the data structure who receives the transformations during the (de)cipher process. This state matrix, in the AES, contains words of 8 bits in a 4x4.

First of all the input (of 128 bits) is cut in this basic words of 8 bits:

There are two ways to modify the size of the input: change the size of the matrix or change the size of the word. Following the article Small Scale Variants of the AES, the two options to reduce the input size from 128 to 32 bits under a Rijndael model:

• Reduce the state matrix to 2x2 (in the AES is 4x4)
• Reduce the word size to 2 bits (in the AES is 8 bits)

But, what's the best way? And there is another question, how big would be the key?

In the AES there are 3 options: 128, 192, 256 bits:

This matrix will be the input of a keyExpansion() function to have the segments of this key to be used in each part of the rounds. 

Why this sizes? Like many of the times, the choice of this 3 sizes corresponds to standardisation reasons like set a small but enough number of them to choose. The original Rijndael supports much more options: you can set a key of 512 bits and structure it into 16 columns in the key matrix. Even 1024 bits key, with 32 columns, the key expanded will still be 44 elements if the number of rows and the number of rounds are still the same.

Furthermore, with a 128 bits block of plain text and key (matrix 4x4 and word size 8) there would be 40 rounds instead of 10. In this case the key expansion will have 164 elements instead of the 44 of the standard. (the number of elements in the key expansion is #columns*#rounds) 

But how to define this parameters in the good direction? Can be the number of rounds be less with in a safety way? Or can some day be necessary to increase this number?

The Rijndael have a good performance over 32 bit hardware. The word size of 8 bits together with the 4 rows who gives 32 bit operation in the ring: . But in deep, the most powerfull feature of the Rijndael from the computation point of view is that it works in the very basic and that means binary.

I hope I'll write soon answering this questions.

Generalization of Rijndael, an introduction

Long time a go I have received a request to prepare a system to encode some data in barcodes. I thought in two options: symmetric cryptography or hash algorithm. But, there where two requirements: "non collision (in between the same key)" and "recover information from the code". Then the choose is made, they can only complained by the symmetric algorithms.

The first symmetric algorithm was to simply operate with an xor operation. But this, as a Vernam type algorithm, is more to a stream ciphering or a one-time pad. Basically means is not the correct algorithm if a key is used more than one time.

To think in the block symmetric algorithms, the old DES, the new AES or any of the finalists in the trial are candidates. I have decided for the Rijndael, the winner of the AES contest. Usually the input/output size on the symmetric algorithms must be as big as possible because the data to cipher is much bigger. For example, in the implementations of the public key cryptosystems is usual to do a hybrid system, and the data is very big. Usually the problem on the symmetrics is to interlace the blocks to avoid patterns between them.

One of the goodness of the Rijndael is the capacity of extension, bigger of smaller. The state matrix, in the standard is 4x4, but the number of rows and columns can be changed. Even more, they can be different between them. The word size, is 8 bits (having operations in 32 bits because 8 bits * 4 elements in a column), but it's possible to do Rijndael with different word sizes.

In the application about I'm working the block size will be below 128 bits, but is not fix having the idea of 64 bits block size. DES is 64 bits block (54 bits effective key size). But why to use a replaced algorithm having the possibility to adapt the Rijndael? Even more, with Rijndael the key size can be also adapted to the needs. But in crypto, any modification must have a previous process of deep think, and a post-process of forever-think.

The Triple-DES was an extension to make bigger the key sizes like 112 or 168 (56 plus 2 or 3 of the simple-DES), and there is an extension for the AES with the name AESWrap (the rfc3394), what can be thing like a sextuple-AES.

There is a difference between DES and AES, and between Triple-DES and the AESWrap. The Rijndael is not only using the key, is also doing an expansion of this key to have more bits as a key. Furthermore, the AESWrap is doing a key derivation function to introduce more dispersion and confusion.

Lets go in the first step of this project: A Generalization of Rijndael to have the data block size parametrizable, also the key size and the number of rounds.

Lets start from the simplification, how to do an Small Rijndael Variant? I have found two articles very helpful on that task:

• Mini Advanced Encryption Standard (Mini-AES): A Testbed for Cryptanalysis (2002) by Raphael Chung-wei Phan
• Small Scale Variants of the AES (2005) by C. Cid , S. Murphy , M. J. B. Robshaw

One book for cryptography developers:

• Cryptography for Developers by Tom St. Denis

And the mandatory books for Rijndael:

• AES Proposal: Rijndael (v2) by Joan Daemen, Vincent Rijmen
• The Design of Rijndael AES - The Advanced Encryption Standard  by Joan Daemen, Vincent Rijmen