avatar  

La encriptación y los números primos

Todos utilizamos sin darnos cuenta los números primos al entrar a nuestra cuenta del banco, al pagar en bitcoins o cuando nos metemos en cualquier web que use el protocolo HTTPS. ¿En qué se usan para estas aplicaciones?
La respuesta es sencilla: en la encriptación.
Para empezar tenemos que repasar qué conocemos por encriptación y cómo funciona.

Encriptación

La encriptación se encarga de, a partir de un mensaje, convertirlo en una maraña de números, letras o cualquier otra cosa que no nos sea fácilmente legible y no nos permita volver al mensaje original de forma fácil ni rápida. Para esto tenemos mil algoritmos que ya se han enfrentado al hecho de convertir mensajes en códigos cifrados y no nos preocupa esta vez.
El problema interesante para nosotros son las claves que se usan en estos algoritmos. Cuando se encripta un mensaje podemos escoger la clave que queremos que se use para cifrarlo, de esta forma si dos personas distintas encriptan el mismo fichero, al haber usado dos claves diferentes, tendrán ficheros encriptados diferentes. Para cada mensaje que queramos cifrar tenemos esencialmente dos tipos de algoritmos: con clave simétrica o con clave pública-privada.
La primera opción es la más simple y también la más rápida, ya que usamos la misma clave tanto para encriptar como para desencriptar. En este caso la clave es escogida por el usuario pudiendo ser una cadena de caracteres cualquiera como la que tendríamos de contraseña en cualquier cuenta de correo u otro servicio.
La segunda opción por contra es mucho más robusta. En esta opción el usuario no puede escoger su clave pública ni privada ya que vienen predeterminadas. Imaginemos que Antonio quiere mandar un mensaje a María. Para esto lo primero que haría Antonio es coger la clave pública de María y encriptar, usando un algoritmo, el mensaje. Tras esto se lo manda a María y a esta solo le resta coger su clave privada y desencriptarlo; fácil. En resumen lo que hacemos es encriptar con la clave pública y desencriptar con la clave privada. Aquí es donde los primos aparecen.
Las claves públicas son generadas usando dos números primos p y q. Se toman estos dos primos y se multiplican, lo que da la clave pública. La clave privada contiene los dos números primos p y q que son los dos únicos factores de la clave pública, es decir p y q son los únicos primos que cumplen que $p\cdot q$ = clave_pública.
A esto se le suma que la forma de encriptar y desencriptar es:

  • C = $M^e$ mod(n)
  • M = $C^d$ mod(n)
    Donde:
  • M es el mensaje en texto plano expresado como un número entero.
  • C es el mensaje encriptado expresado como un entero.
  • n es el producto de p y q.
  • d es un número entero aleatorio primo relativo con $(p-1)\cdot (q-1)$ (esto es que su máximo común divisor sea 1).
  • e es el inverso multiplicativo de d.

Resumiendo: usamos $p\cdot q$ como clave pública y p y q como clave privada.
Ahora imaginemos que una tercera persona quiere desencriptar el mensaje dirigido a María sólo conociendo la clave pública. Esto lo que nos deja es que necesitamos factorizar la clave pública para obtener la clave privada, suena fácil, ¿verdad?
Estos cálculos evidentemente no son tan sencillos. El algoritmo más fácil para buscar un primo (en el caso general) es tomar todos los números que estén por debajo de la raíz cuadrada e ir probando uno a uno si son divisores de nuestro número.
Por ejemplo si tenemos el número 1459160519 tendríamos que comprobar hasta el número 38199, lo cual sería fácilmente computable por un ordenador. Date cuenta de que hemos tomado un número de 10 dígitos. Ahora vamos a tomar uno de 400 (el primo más grande conocido tiene 22,338,618 dígitos). Si tomamos uno de 400 tenemos que la raíz cuadrada tiene 200 dígitos. El tiempo de vida del universo es $10^{18}$ segundos, por lo que si asumimos que un ordenador comprueba un millón de divisores por segundo tenemos que podemos comprobar $10^{24}$ posibilidades en todo el tiempo de vida del universo. En un número de 400 dígitos son $10^{200}$ posibilidades para probar, por lo que necesitaríamos ejecutar nuestro programa $10^{176}$ veces el tiempo de vida del universo.
Ahora estamos un terreno cómodo, ya que con primos relativamente grandes (100 dígitos o más), con los métodos actuales no es posible hallar en un tiempo razonable la descomposición en primos.

Por lo tanto si queremos hacer sistemas de encriptación muy seguros tenemos que tomar primos lo más grandes posibles, Mersenne nos va a ayudar.

Primos de Mersenne

Para hallar números primos muy grandes no podemos ir probando todos los números en orden, ya que no sería computable en un tiempo razonable.
Mersenne (1588-1648) propuso que los números de la forma $2^p-1$ podían ser primos, sabiéndose en la actualidad además que tienen propiedades muy deseables para eliminar candidatos que no sean primos.
Como ejemplo podemos poner que $2^{2} - 1 = 3$ es un primo de Mersenne y $2^3 - 1 = 7$ lo es también.
Esta es la forma actual en la que hallamos primos muy grandes siendo el último hallado en Enero de 2016 con 22.338.618 dígitos y siendo este número $2^{74.207.281} - 1$.
Estos primos pueden llegar a ser un poco difíciles de manejar, pero son muy útiles y podemos usarlos para sistemas muy robustos de encriptación. Actualmente la asociación GIMPS tiene una red distribuida para hallar primos de Mersenne que tiene el récord de haber hallado el último número primo mencionado anteriormente.
Los números de Mersenne tienen propiedades muy buenas que nos permiten calcular muy rápido estos primos como se puede observar en un programa de prueba que he hecho. Si quieres aprender mas puedes echar un ojo al repositorio anterior y mirar la web de GIMPS donde explican de forma muy didáctica cómo los comprueban.

Las matemáticas son una herramienta esencial a la hora de defender nuestra privacidad y anonimato.

#somosruido
#wearenoise

avatar  

Distributed Ledger and ethereum token creation

Basically, distributed ledger is the concept of sharing data evolution control in a common network. One of the most famous examples of this are BITCOINS, which works over a blockchain, a data base distributed between several participants (nodes) inside a ledger, which contains the updated status of each transaction between the nodes. These nodes are connected using a specific protocol.

The key of this system’s movement lays on Token, elements that contains information and are encrypted. This token could act as a currency, vote, message, or anything that can be fixed in Distributed Ledger system. Several startups saw in this model new opportunities and efficient ways to approach to a better security and lower cost solutions. This way, DL is not always pictured in currency terms, but also thought to be an interesting option in energy industry (Powerledger), IoT (Filament), communication or Voting systems (Horizon State).

Beware! Shitty diagram incoming:

Ethereum (an uprising cryptocurrency) has a wallet application that let developers freely deploy c++ contracts for token creation or nodes organizations in a virtual sandbox or in the real world. This is a lot of fun and makes the understanding of distributed ledger clearer for developers. The original documentation can be found here and here, and I will sum up how to create a token contract. Also, there’s a wider explanation about DL in spanish and some contract examples in my github repository, please feel free to take a look at it and suggest any issues or PR. The project development is also pictured in a kanban styled board in the repo.

Okay so the basic token contract handles the initial supply of tokens that the owner (the contract developer) has, and the basic transfer funtion that includes checkings and token ownership changing.

contract MyToken {
    /* This creates an array with all balances */
    mapping (address => uint256) public balanceOf;

    /* Initializes contract with initial supply tokens to the creator of the contract */
    function MyToken(
        uint256 initialSupply
        ) {
        balanceOf[msg.sender] = initialSupply;              // Give the creator all initial tokens
    }

    /* Send coins */
    function transfer(address _to, uint256 _value) {
        require(balanceOf[msg.sender] >= _value);           // Check if the sender has enough
        require(balanceOf[_to] + _value >= balanceOf[_to]); // Check for overflows
        balanceOf[msg.sender] -= _value;                    // Subtract from the sender
        balanceOf[_to] += _value;                           // Add the same to the recipient
    }
}

But for creating a more complex cryptocurrency (that can be also used for other purposes such as voting, as mentioned) we should settle down some more details. For example, we should define the basic variables for the token identification:

// Public variables of the token
string public name;
string public symbol;
uint8 public decimals = 18;
// 18 decimals is the strongly suggested default, avoid changing it

And a more conplex transfer function which takes cares of saving balances for the future.

function _transfer(address _from, address _to, uint _value) internal {
    // Prevent transfer to 0x0 address. Use burn() instead
    require(_to != 0x0);
    // Check if the sender has enough
    require(balanceOf[_from] >= _value);
    // Check for overflows
    require(balanceOf[_to] + _value > balanceOf[_to]);
    // Save this for an assertion in the future
    uint previousBalances = balanceOf[_from] + balanceOf[_to];
    // Subtract from the sender
    balanceOf[_from] -= _value;
    // Add the same to the recipient
    balanceOf[_to] += _value;
    Transfer(_from, _to, _value);
    // Asserts are used to use static analysis to find bugs in your code. They should never fail
    assert(balanceOf[_from] + balanceOf[_to] == previousBalances);
}

A function to destroy the tokens (the ones the participant owns) from the system (no take back!) or the ones from another participant.

function burn(uint256 _value) public returns (bool success) {
    require(balanceOf[msg.sender] >= _value);   // Check if the sender has enough
    balanceOf[msg.sender] -= _value;            // Subtract from the sender
    totalSupply -= _value;                      // Updates totalSupply
    Burn(msg.sender, _value);
    return true;
}

function burnFrom(address _from, uint256 _value) public returns (bool success) {
    require(balanceOf[_from] >= _value);                // Check if the targeted balance is enough
    require(_value <= allowance[_from][msg.sender]);    // Check allowance
    balanceOf[_from] -= _value;                         // Subtract from the targeted balance
    allowance[_from][msg.sender] -= _value;             // Subtract from the sender's allowance
    totalSupply -= _value;                              // Update totalSupply
    Burn(_from, _value);
    return true;
}

Also, a nice function would be the one who settles POW (proof of work) for getting the tokens and signing the transactions.

uint current = 1; // hehe try to guess the cubic root of the number. Imposible task >:)

    function rewardTheGenious(uint answer, uint next) {
        require(answer**3 == current); // goes on if it's correct
        balanceOf[msg.sender] += 1;         // reward the user!
        current = next;   // next test
    }

But unfortunately a computer finds this very easy, so maybe we should create a better Proof of work, that supposses a real challenge for a machine (those filthy smart toasters!):

    bytes32 public currentChallenge;                         // The coin starts with a challenge
    uint public timeOfLastProof;                             // Variable to keep track of when rewards were given
    uint public difficulty = 10**32;                         // Difficulty starts reasonably low

    function proofOfWork(uint nonce){
        bytes8 n = bytes8(sha3(nonce, currentChallenge));    // Generate a random hash based on input
        require(n >= bytes8(difficulty));                   // Check if it's under the difficulty

        uint timeSinceLastProof = (now - timeOfLastProof);  // Calculate time since last reward was given
        require(timeSinceLastProof >=  5 seconds);         // Rewards cannot be given too quickly
        balanceOf[msg.sender] += timeSinceLastProof / 60 seconds;  // The reward to the winner grows by the minute

        difficulty = difficulty * 10 minutes / timeSinceLastProof + 1;  // Adjusts the difficulty

        timeOfLastProof = now;                              // Reset the counter
        currentChallenge = sha3(nonce, currentChallenge, block.blockhash(block.number - 1));  // Save a hash that will be used as the next proof
    }

Once our token looks just like we wanted we can deploy it using the ethereum wallet sandbox. The interface is quite simple, only add the code in the editor box, fill the options you coded (name or symbol, for example, good news you can use emoticons!) and click in Deploy. For this only set the correct Network (virtual sandbox, there are a couple), click on contracts and look for the “DEPLOY NEW CONTRACT” button.

Anyway I think as a research experiment to better understand the criptocurrencies is pretty neat. I aim to write a refined token contract on my own as well as a contract to organize several nodes in the blockchain. Hope you guys found it as fun as I did!

avatar  

A por los twiteros

Esta afirmación puede ser atribuida a varios políticos y personajes del ámbito público en la actualidad. Últimamente hemos tenido muchos casos en los que, usuarios de las redes sociales (sobre todo Twitter), han sido juzgados por sus comentarios en estos medios.
El ámbito del juicio y las repercusiones legales que pueden sufrir estas personas recaen en los jueces y no es mi intención tratarlas en este artículo. Entonces, ¿de qué va esto?

Recientemente he visto a políticos afirmar en medios de comunicación que todos los usuarios de las redes sociales deberíamos identificarnos en las mismas, con la intención de que los insultos en las redes sociales no queden impunes y no nos amparemos en el anonimato.
Todo está mal.

Hay varios motivos por los que esta afirmación no es correcta y más aún, es peligrosa.
En primer lugar las redes sociales no son anónimas, ya que hay muchos factores que nos identifican y se nos piden o se obtienen de nosotros, por ejemplo: número de teléfono, dirección, IP …
Todo esto hace que identificar a una persona en las redes sociales sea posible, ya que además las mismas plataformas suelen ceder los datos ante peticiones judiciales de los mismos.
Entonces, ¿cuál es el problema?

Las redes sociales de por sí ya tienen suficiente información sobre nosotros, ¿qué pasaría si le tuviéramos que dar nuestro documento de identidad?
En primer lugar podrían comprar datos a otras empresas (que sí tienen nuestro documento de identidad) como bancos, tiendas online, servicios médicos privados, etc.

Esto implicaría que Google, Facebook, Twitter y todas las redes sociales más extendidas podrían saber si padecemos una enfermedad, si tenemos seguro, qué coche conducimos, qué ingresos tenemos, dónde trabajamos …
Ya ha dejado de ser una buena idea, ¿verdad?

No quiero particularizar el caso en ningún partido político, ya que no es necesario para estas reflexiones. Lo que quiero provocar en vosotros es un ánimo crítico cuando escuchamos a algún político hablar sobre Internet, redes sociales o privacidad.
La mayoría de los gobernantes que tenemos no tienen una idea general de cuáles son las repercusiones de estas afirmaciones tan graves que a veces dan en un calentón verbal.

Respetad nuestra privacidad
#somosruido
#wearenoise

avatar  

¡Hola! Hoy os venimos a hablar de móviles, una de las claves de la vigilancia masiva en el tiempo que estamos.

Como ya sabemos, una de las claves para defenderse de la vigilancia masiva es usar el máximo posible de software libre, ya que este está continuamente auditado por la propia comunidad e incluso uno mismo es capaz de ver el código fuente.

En los móviles, por desgracia, esta no es la tónica general y, aunque el proyecto Android sea libre, las aplicaciones de Google que vienen en todos los teléfonos que compramos, no lo son. Menos aún si vienen otras como Facebook, etc. Además, los fabricantes de móviles suelen añadir capas a Android para modificar su funcionamiento o estética, y también para mandar datos a la propia compañía, como por ejemplo sobre cómo usas el teléfono, cuánto te dura la batería con ese uso, qué aplicaciones tienes instaladas… De esa información se pueden inferir muchos datos íntimos que, por desgracia, luego se pueden usar para venderlos y añadirlos a nuestros perfiles. =( Puedes ver esto que escribió Stallman al respecto hace ya varios años.

¿Cómo librarse de todo este software espía, entonces? Pues existen varias alternativas, y en función de tu dispositivo, puede que incluso te liberes al 100%.

Como mejor opción está Replicant: una versión de Android 100% libre y avalada por la FSF. Por desgracia, al ser todo libre en esta versión de Android, los controladores del hardware solo funcionan en una lista muy reducida de dispositivos, y además no todas las funcionalidades. Recogen todos los detalles en esta lista.

También tienes la opción de instalar algún derivado del AOSP (Android Open Source Project), como LineageOS, que es una versión, en esencia, libre, pero hace uso de todos los controladores privativos en los dispositivos que soporta.

¿Cómo se hace todo esto? Pues depende de la versión que vayas a instalar. En la wiki de estos proyectos tienes un montón de información de cómo hacerlo para cada dispositivo, así que lo mejor que puedes hacer es buscar en las páginas de los proyectos.

Por cierto, en todos los móviles la instalación requiere en algún momento ganar permisos de administrador (rootear) o desbloquear el cargador de arranque (bootloader). Para esto, algunos fabricantes (Motorola, por ejemplo) te hacen pedirles un código y te dicen que la garantía queda invalidada a partir de ese momento. Lo cierto es que esto es mentira en Europa, y puedes encontrar toda la información al respecto en esta entrada de la FSF Europe.

¡Anímate y libera tu móvil! =)

avatar  

Cuando subimos contenido a las redes sociales, es común plantearse si esos datos serán revisados en un futuro por amigos, pareja, familia, o incluso que puedan ser juzgados por compañeros de trabajo, compañías de seguros, recursos humanos… Es innegable que las redes sociales tienen un fuerte impacto en nuestra forma de relacionarnos, y sin duda nuestras intervenciones digitales están directamente relacionadas con nuestra vida.

En los últimos años, una disciplina concreta de la informática, Big Data, ha ocupado la atención de muchos profesionales del sector, puesto que la gran cantidad de información que generamos tienen múltiples utilidades. Si bien el estudio de estos datos puede abrir muchas puertas a la innovación y la tecnología, como toda herramienta con potencial, tiene sus peligros. La recolección de datos masiva sin consentimiento de los individuos, así como los términos y condiciones difusos sobre el tratamiento de estos datos en algunas ocasiones, son un ejemplo del mal uso de esta tecnología.

Dentro de este grupo de uso indebido de Big Data, nos encontramos con SCS (Social Credit System), un modelo de ficción distópica llevada a la realidad. La idea de este sistema consiste en puntuar el nivel de civismo de tus “contactos” (bien pueden ser compañeros de trabajo, amigos, familiares u otros conocidos) y que éstos, a su vez, te puntúen. El objetivo de los puntos es acceder a ventajas fiscales, facilidades de visados, acceso a entrevistas de trabajo, chequeo “exprés” en aeropuertos y otras “recompensas” similares. Este sistema es una realidad que el gobierno Chino quiere instaurar como obligatorio a partir de 2020. Dicho gobierno argumentaba que el objetivo de dicho sistema es “permitir a aquellos dignos de confianza vagar a cualquier sitio bajo el cielo al mismo tiempo que complicarle cada paso a aquellos que estén desacreditados”. Aunque se describió en principio como una monitorización civil sobre cosas como el fraude al estado, cruzar indebidamente y similar, se pretende aumentar el rango de vigilancia incluso al tráfico de internet.

Actualmente existen pequeños modelos de está técnica, por ejemplo, en un barrio de Shangai hay un sistema mediante el cual se listan a los “vecinos ejemplares” cada semana basándose en su comportamiento. En contrapunto a la clara violación de la privacidad, se especula con la posibilidad de que este sistema fuera capaz de disminuir casos de corrupción en empresas y organismos, otro problema destacable en el país. Sin embargo esta posibilidad apenas es una solución, teniendo en cuenta los recursos y la intrusión necesarios para hacerlo realidad.

Ante una situación que se presenta tan extrema, cabe preguntarse hasta qué punto puede influir en la sociedad y en cada individuo un sistema radicalmente intrusivo, y preguntarse si de verdad algo así es funcional, o por el contrario (en caso de que llegue a hacerse realmente en 2020, como ha indicado el gobierno) generará un hastío de la población y una consecuente respuesta.