Independent Submission                                       M. Fabbrini
Internet-Draft                                              May 20, 2023
Intended status: Informational
Expires: November 16, 2023

       FC1 Algorithm Ushers In The Era Of Post-Alien Cryptography



   This memo aims to introduce the concept of "post-alien cryptography",
   presenting a symmetric encryption algorithm which, in our opinion,
   can be considered the first ever designed to face the challenges
   posed by contact with an alien civilization. FC1 cipher offers an
   unprecedented grade of confidentiality. Based on the uniqueness of
   the modular multiplicative inverse of a positive integer a modulo n
   and on its computability in a polynomial time, this non-deterministic
   cipher can easily and quickly handle keys of millions or billions of
   bits that an attacker does not even know the length of.
   The algorithm's primary key is the modulo, while the ciphertext is
   given by the concatenation of the modular inverse of blocks of
   plaintext whose length is randomly chosen within a predetermined
   range. In addition to the full specification here defined, in a
   related work we present an implementation of it in Julia Programming
   Language, accompanied by real examples of encryption and decryption.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on May 20, 2023.

Fabbrini                 Expires November 16, 2023              [Page 1]

Internet-Draft         FC1 Post-Alien Cryptography              May 2023

Copyright Notice

   Copyright (c) 2022 IETF Trust and the persons identified as the
   document authors. All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   ( in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  2
   2.  The Need Of A Post-Alien Cryptography  . . . . . . . . . . . .  3
   3.  Specification  . . . . . . . . . . . . . . . . . . . . . . . .  5
     3.1.  Modular Multiplicative Inverse . . . . . . . . . . . . . .  5
     3.2.  Description  . . . . . . . . . . . . . . . . . . . . . . .  5
        3.2.1.  Encryption  . . . . . . . . . . . . . . . . . . . . .  5
        3.2.2.  Decryption  . . . . . . . . . . . . . . . . . . . . .  7
     3.3.  Recommended Parameters Set . . . . . . . . . . . . . . . .  7
   4.  Implementation And Tests . . . . . . . . . . . . . . . . . . .  8
   5.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  8
   6.  Security Considerations  . . . . . . . . . . . . . . . . . . .  8
   7.  Informative References . . . . . . . . . . . . . . . . . . . .  9
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . .  9

1.  Introduction

   In a symmetric key encryption scheme, a single key is used for both
   encryption and decryption. An algorithm can be considered safe if the
   only way to guess the key is to explore all the possibilities given
   by the different combinations of zeros and ones. This is called a
   "brute-force attack" and under certain circumstances it can be very
   difficult, if not impossible, to implement. A 256-bit key (the length
   used by the current AES encryption standard) is at present considered
   "unbreakable" even by the next generation of quantum computers. So it
   appears that approved standards can ensure a good level of
   confidentiality for many decades to come. Neverthless, if we look at
   some structural aspects of them, we can find some relevant weaknesses
   that could jeopardize the security of encrypted data in light of some
   new challenges that we are likely to face in a near future. But

Fabbrini                 Expires November 16, 2023              [Page 2]

Internet-Draft         FC1 Post-Alien Cryptography              May 2023

   before going into the technical details of the weaknesses, it is
   useful to dwell on the implicit hypothesis that underlies the alleged
   security of encryption standards. In fact, they are designed to
   instantly transfer encrypted data between two different points in
   space. But if we consider sending data to a different point in time,
   then the algorithms used would be perhaps inadequate to protect the
   confidentiality of the original text. For example, suppose Alice
   wants to transmit an AES-256 encrypted message to Bob who will use
   the symmetric key to decrypt it in 50 years. How can Alice be sure
   that the technological development of the coming years will not lead
   to the ability of testing 2^256 different sequences of 0's and 1's
   in a reasonable time, so making the key in Bob's possession useless?
   Now let's see the structural aspects that may compromise the safety
   of the accepted standards. Current standards have four main aspects
   in common. The first two are related to the key: its length is known
   and does not exceed 256 bits. The last two relate to the algorithms:
   they are deterministic and convert a fixed block of plaintext into a
   ciphertext block of the same length. An algorithm is deterministic if
   a given plaintext always produces a given ciphertext. These four
   points are generally considered irrelevant and do not raise security
   concerns. In our opinion, there are however two specific scenarios
   that could change the rules of the game. The first one, which we call
   the "internal" scenario, relates to the prospect of an upcoming world
   war, or at least of a long period of involution in the reciprocal
   relations among states. A tragic war is hitting Europe. Again.
   Diplomatic relations are cooling down and scientific discoveries
   become military secrets. In this context of separation and conflict,
   how can one be sure that a certain technological level has not
   already been reached by the adversary?  So, for example, how can we
   be sure that no one in the world is able to test 2^256 different
   possibilities in a reasonable time? But if the internal context is
   worrying, perhaps the "external" one is even more so. By "external"
   scenario we refer to the possibility of an encounter with an alien
   civilization that could render current encryption schemes
   ineffective, thus posing serious security risks for the entire human
   species. FC1 was designed by imagining attackers possessing a
   computational capacity far superior to that of our present and future

2.  The Need Of A Post-Alien Cryptography

   Imagine waking up tomorrow and discovering aliens exist, they're here
   and they're not good guys. Then you decide to join others to organize
   a resistance. The first thing you realize is that you need a secure
   communication channel to coordinate with others. The second bad news
   of the day is to understand that the AES-xxx is unable to protect
   your messages because the aliens use cryptanalytic techniques and

Fabbrini                 Expires November 16, 2023              [Page 3]

Internet-Draft         FC1 Post-Alien Cryptography              May 2023

   computing power capable of breaking any deterministic algorithm.
   But without imagining alien invasion scenarios, let's think about
   how much the chances of a first contact with aliens will increase
   thanks to the synergy between the public and private sectors in
   space trips. Humanity is about to become a multiplanetary species and
   soon our spaceships will venture into deep space in search of planets
   to explore and on which to perpetuate the human race. It is logical
   to assume that aliens are technologically more advanced than us and
   have perhaps another math, but that they are able to understand ours.
   It also makes sense to assume that however advanced their
   computational abilities are, they are somehow "bounded". Since a
   brute-force attack implies in any case the use of computing power,
   it may be a good idea "to raise the bar", thus passing from keys of
   256 bits to keys of hundreds of thousands or millions of bits.
   Likewise, it can be helpful not to publicly disclose the key length.
   But in the face of considerable computing power, the use of a larger
   key may not be sufficient. It is necessary to break the mold and move
   without delay from deterministic to non-deterministic algorithms,
   making the relationship between input and output more complex and
   unpredictable. These are the main lines that have guided the
   construction of the FC1 algorithm, the first one we made public in a
   class of algorithms designed to face the exciting challenges of our
   We believe that FC1 ushers in the era of "post-alien cryptography"
   and we hope that the debate we have stimulated will lead to realize
   we need to have a vision oriented to the design of algorithms that
   can defend human life from any possible threat.

3.  Specification

3.1.  Modular Multiplicative Inverse

   Definition - For a positive integer n, and a (an element of Z) we say
   that a' is a multiplicative inverse modulo n if

                      a*a' is congruent to 1 mod n

   It can be proven [1] that:

      1. a has a multiplicative inverse modulo n if and only if a and n
         are relatively prime
      2. if a' exists, then it is unique

   Computation - There are various methods to compute the inverse modulo
   n in a polynomial time [2] [3] which, if implemented in languages
   like Julia, having built-in support for Arbitrary Precision
   Arithmetic, make it possible to calculate a' in a few fractions of a

Fabbrini                 Expires November 16, 2023              [Page 4]

Internet-Draft         FC1 Post-Alien Cryptography              May 2023

   second even for numbers with hundreds of thousands of digits.

   A note on Julia Programming Language - With origins in the Computer
   Science and Artificial Intelligence Laboratory (CSAIL) and the Dep.
   of Mathematics, Julia is a programming language created in 2009 by
   Jeff Bezanson, former MIT Julia Lab researchers Stefan Karpinski, and
   Viral B. Shah, and professor of mathematics Alan Edelman. The Julia
   programming language is a flexible dynamic language, appropriate for
   scientific and numerical computing. Julia provides software support
   for Arbitrary Precision Arithmetic, which can handle operations on
   numeric values that cannot be represented effectively in native
   hardware representations, but at the cost of relatively slower
   performance. To allow computations with arbitrary-precision integers
   and floating point numbers, Julia wraps the GNU Multiple Precision
   Arithmetic Library (GMP) and the GNU MPFR Library, respectively.
   In an APA application the size of the integer is limited only by the
   available memory.

3.2.  Description

   Basic concept - FC1 essentially relies on the uniqueness of the
   modular multiplicative inverse of a positive integer a modulo n and
   on the fact that it can be calculated in a polynomial time. Here the
   modulo is the main key which, due to the algorithm's design, can be
   any positive integer, while the ciphertext is the modular
   multiplicative inverse. The plaintext, once tagged with a hash, is
   divided into blocks, the length of which is chosen by a random number
   generator, converted into ciphertext and sent over an insecure

   Keys - Keys to be kept secret and transferred over a secure channel
   are primary key (the modulo) and secondary key. The latter represents
   the length of a random string that is placed at the beginning of the

3.2.1  Encryption

   Hash - The very first operation that is performed is the computation
   of a hash of the plaintext using the SHA-256 function. This tag is
   then appended at the end of the text. The purpose is to ensure the
   integrity of the data transmitted. We denote the plaintext with the
   final tag by 'tplain':

                        tplain = plaintext || hash

   Ciphertext initialization - With the value of the secondary key, a
   random string is created which we denote by 'startpad'. This is the
   initial ciphertext:

Fabbrini                 Expires November 16, 2023              [Page 5]

Internet-Draft         FC1 Post-Alien Cryptography              May 2023

                              c = startpad

   Fencrypt - A main function named 'fencrypt' has the task of
   controlling the flow, switching between different sections of the
   algorithm in relation to a certain threshold value of the length of
   the tagged plaintext that still remains to be encrypted. The
   threshold is fixed at 1.5 times the length of the modulo.

   Frand - In the first part of the algorithm fencrypt calls a random
   number generator in a given range, which we denote by 'frand'. The
   generated random integer represents the length of the i-block of
   tagged plaintext to be encrypted. We denote by |modulo| the length of
   the modulo. The frand function generates a random value between 1 and
   |modulo| − 3. From the length of the modulo, 3 bits are subtracted to
   define the upper limit of the random function because 2 bits space is
   used to append the leading and trailing 1 (see next point 'Fintgen').
   Moreover, since we want that the integer, whose modular inverse we
   are going to calculate, is less than the modulo, another bit is

                      1 =< frandvalue =< |modulo| - 3

   Fintgen - A leading and a trailing '1' are appended at each chunk of
   tagged plaintext whose length is randomly selected by frand function.
   The leading 1 is meant to make sure that the input of the function
   computing the modular inverse is a positive integer since the block
   could start with '0'. The trailing '1' serves to prevent the
   algorithm from blocking in the case of an even modulo and a tagged
   plaintext to be encrypted containing a long row of 0's. We denote by
   tplain_i the i-block of tagged plaintext; then is:

                       input_i = 1 || tplain_i || 1

   Finv - Once the input has been prepared, it is possible to attempt to
   compute the modular inverse using the 'finv' function. If the input
   and the modulo are not coprime, finv cannot produce a result and it
   calls the main function fencrypt which calls frand again in order to
   try with a different random integer. Else, if they are coprime, the
   modular multiplicative inverse is computed in a polynomial time and
   passed to the next step.

   Fblockgen - If the modular inverse is computable, a function called
   'fblockgen' comes into play comparing the modulo length with that of
   the modular inverse generated by finv. If the lengths are the same,
   fblockgen does not modify the string:

   If |modulo| = |finvvalue|_i

Fabbrini                 Expires November 16, 2023              [Page 6]

Internet-Draft         FC1 Post-Alien Cryptography              May 2023

                         output_i = finvvalue_i

   Otherwise, if the modular inverse length is less than modulo length,
   fblockgen adds one or more leading zeros so that the lengths match:

   If |modulo| > |finvvalue|_i

                      output_i = 0..0 || finvvalue_i

   Final step of the first part - The block created by fblockgen is
   concatenated to the existing ciphertext and the main function
   fencrypt is called.

   Second part: ciphertext finalization - When threshold is crossed, the
   finalization functions are called. They have the task of
   simultaneously calculating the last and the second-last block of
   ciphertext. This design solution is necessary to prevent the case the
   modular inverse does not exist for the last portion of tagged
   plaintext, with the consequence of blocking the whole encryption
   process. The last step involves adding a random final padding whose
   length must be less than modulo length. This final padding, that we
   call 'endpad', is actually a third key that we can consider inferred
   from the other two. It is automatically added by the encryption
   algorithm. In the subsequent decryption phase, the algorithm will
   recognize it as its length is less than that of the modulo and
   finally it will discard it without attempting to decrypt it.

   Encryption flowchart - A detailed flowchart of the encryption process
   is provided in our related work [4].

3.2.2  Decryption

   We omit a complete description of the decryption algorithm since it
   is trivial. Note that, once the whole tagged plaintext has been
   decrypted, it is checked, through the hash function, that the final
   tag is correct and that therefore the integrity of the data is not

3.3  Recommended Parameters Set

   Primary key - We recommend a minimum length of 501 bits. At the same
   time, we encourage the use of 50.000-100.000 bits keys to fully
   exploit the potential offered by the algorithm. To maximize the speed
   we suggest the use of a modulo having as factors non-trivial prime
   numbers. If, on the other hand, the aim is to create further problems
   for a potential attacker, we recommend the inclusion of some trivial
   factors such as 3, 5, 11 and so on. Remember that you can safely use
   an even modulo without absolutely slowing down the algorithm.

Fabbrini                 Expires November 16, 2023              [Page 7]

Internet-Draft         FC1 Post-Alien Cryptography              May 2023

   Secondary key - It has no upper limit and can even be 0.

4.  Implementation And Tests

   We have coded the algorithm in Julia Programming Language and tested
   it using keys of different length, from 10.000 bits to over bits. Both the code and some of the tests were recently
   published in a paper, available on IACR [4].

5.  IANA Considerations

   This memo includes no request to IANA.

6.  Security Considerations

   The minimum recommended primary key length we have seen is 501 bits.
   The maximum length is instead not defined because it depends on the
   limits of the system on which the algorithm is run. In our tests we
   went as far as keys of over one Gigabit, which means a length of over
   a billion of bits. Now, if by hypothesis the attacker knew the length
   of the key, the startpad was zero and he could have any information
   about the content of the first block of plaintext, for a brute-force
   attack he would have to try about 2^ different
   combinations. Since the attacker does not normally know the length of
   the key, assuming the startpad equals zero, the number of attempts
   would be:

          SUM [2^i] from i = 501 - 1, to i = - 1

   We denote by |maxmodulo| the longest key that a system can handle in
   a 'reasonably short time' and by |minmodulo| the minimum recommended
   length of the primary key.
   Generalizing and assuming that |tplain| > |maxmodulo| we have:

       SUM [2^i] from i = |minmodulo| - 1, to i = |maxmodulo| - 1

   FC1 therefore provides an incredible grade of confidentiality,
   compared to the standards currently in use, which makes it suitable
   for facing the difficult challenges of the next future. As far as
   integrity is concerned, it is ensured by adding a tag generated by a
   SHA-256 function. In a future work we will discuss in detail other
   possible attacks (such as the 'replay attack') and we will show how
   FC1 is immune to them.

Fabbrini                 Expires November 16, 2023              [Page 8]

Internet-Draft         FC1 Post-Alien Cryptography              May 2023

7.  Informative References

   [1] Victor Shoup (2009) A Computational Introduction to Number Theory
       and Algebra, Cambridge University Press; 2nd ed.
   [2] Michele Bufalo, Daniele Bufalo, Giuseppe Orlando (2021) A Note on
       the Computation of the Modular Inverse for Cryptography, Axioms
   [3] Niels Moeller (2007) On Schoenhage's algorithm and subquadratic
       integer GCD computation, MATHEMATICS OF COMPUTATION
   [4] Michele Fabbrini (2022) FC1: A Powerful, Non-Deterministic,
       Symmetric Key Cipher, Cryptology ePrint Archive, Report 2022/567

Author's Address

   Michele Fabbrini

Fabbrini                 Expires November 16, 2023              [Page 9]

Internet-Draft         FC1 Post-Alien Cryptography              May 2023