Well, there would be two possible ways to use modular arithmetic:

You could do the arithmetic modulo $2^n$.  However, that has some nasty properties (not all elements have multiplicative inverses, higher order bits do not affect lower order ones), and while you could get around these issues, it would require significant changes to AES.
You could do the arithmetic modulo a prime $p$.  That avoids the above issues, however the issue here is that our plaintext and ciphertext blocks are even sets of bits; elements modulo a prime $p$ are not (except for $p=2$, which doesn't sound interesting).  Hence, you'd need to add some special logic to handle that.

By using $GF(2^8)$, they avoid all the above issues; all nonzero elements have inverses, in a multiplication (or inverse), every input bit potentially affects every output bit, and a part of a block fits nicely in a field element.


Combining a block cipher with a (pseudo) OTP

There's quite a few things wrong with this. For starters, a block cipher does not imply authentication. Common block cipher modes such as CTR, CBC, and (god forbid) ECB provide nothing but pure encryption. If you want authentication, look into the GCM block cipher. AES-GCM is possibly the better way to go here.

You state that it is built on the idea that every bit is important when deciphering the data, but this is simply not true. It is difficult (to my knowledge) to have a block cipher rely on every bit of the ciphertext for decryption to be successful. The best thing you can get is having a block cipher rely on every previous bit, meaning you can decrypt the first half of the data just fine while ignoring the second half.

If you have a working OTP, why are you bothering with a block cipher? Just digitally sign it or use a MAC and it will be authenticated. Other than that, an OTP provides perfect secrecy. (Don't be fooled, this is for a perfect OTP, which is virtually impossible to do correctly)

If you are dead set on your OTP & block cipher combo, then I suggest using AES in GCM mode as your block cipher, followed by a newly generated OTP (or a removed section of an existing OTP generated for use in encryption).

However, AES-GCM alone will do what you are looking for without the need of a OTP. And considering how difficult it is to pull off using a real OTP, it's probably more secure just sticking with AES.


Best practises to generate IV for AES-CTR in this scenario

You may want to rethink your whole setup. Like mentioned in the comments, there is a lot more to securely storing files than throwing encryption on them. In particular, you need to be concerned with authentication (CTR without authentication is malleable). I would also look into client side encryption in anything that puts user data in the cloud.

Still, there are probably some situations where just using CTR to encrypt a bunch of files is the right thing to do, so I will answer your questions below.

  What's the best practise in this scenario to derive the IV (or maybe a Key + IV)?

Usually in CTR mode you have a nonce concatenated with a counter. If you want to support arbitrary file sizes, you probably want the counter to be 64 bits. However, that does not leave enough space for a nonce, since 64-bit nonces will collide after a few billion files. If e.g. your API restricts you to this setup, you would be better off with per-file keys.

If you can use random 128-bit nonces, with e.g. the lower half incremented as the counter, that should be fine. You would avoid the need for key setup, which would be an advantage especially with small files.

  If key mustn't be the same, would it be secure to do the following:

  A new key (256-bit) is randomly-generated for every file.
  This key is encrypted with the masterkey in ECB mode (since it's highly entropy data, do we need CBC?)
  The file key is appended at the beginning of the file.

ECB would be acceptable for encrypting random data, but concerns about authentication remain. Alternatively you could use key derivation. That way you can use e.g. a random 128-bit salt for each file even with 256-bit keys.


How secure is the AES master key if Round Keys are found

If an attacker find some round key of AES256. Is it possible to find the master key ?

If the attacker is given a single round key from an 256 bit AES key, it is infeasible to reconstruct the full key (even if you have access to chosen plaintext/ciphertext against the full key).

This single round key reduces the number of possible AES keys from $2^{256}$ to $2^{128}$; however a search over the remaining 128 unknown bits would be computationally infeasible.  In addition, there is no obvious way to use you single known round to aid a Pt/Ct attack, because while there's a subkey which you know the key, there are 14 subkeys which you have no information on (AES-256 has 14 rounds, but 15 round keys).  Known "chosen key" attacks on AES-256 involve modifying the key; there's no obvious way to exploit that here.

  How safe is the master key if an attackers finds multiple round keys?

That's different; if the attacker finds two adjacent subkeys, then it's game over; he can trivially reconstruct everything.  For AES-256, each round key is an easily computed function of both the previous two round keys, or the next two round keys; hence with two adjacent round keys, you can reconstruct everything.  In fact, some hardware AES-256 implementations store two subround keys; the first two for encryption, and the last two for decryption; they reconstruct all the other round keys on the fly during the en/decryption process.

Now, what if the attacker finds two subkeys, but they're not adjacent?  Well, that's not quite as clear.  My instincts tell me that would be safer to assume that the attacker is able to recover everything, but how easy that really is might depend on how close the exposed rounds are; if they have a gap of one, you ought to be able to trivially reconstruct the round key between the two; if what's exposed is the first and last round keys, it might be a tad trickier.


Can the knowledge of the inverse of $p$ modulo $q$ help factor $n=pq$?

This question was already answered in this not-so-great titled question.

($p$ and $q$ being "safe primes" does not matter in this context, but $q$ shouldn't be (much) longer than $p$, as the methods works for $q<p$, but can be adapted by "guessing" the top bits of $q$ otherwise).


Why does square root $\pmod n$ find $p$ and $q$ (as $n = p \cdot q$)?

If $x^2\equiv1\mod{n}$, it means that $(x+1)(x-1)\equiv0\mod n$. In other words, $(x+1)(x-1)=k\cdot n=k\cdot p\cdot q$ for some $k\in\mathbb{N}$. And there you go: if $x\neq\pm 1\mod n$, neither $x+1$ nor $x-1$ equals $p\cdot q$ and must contain either of the primes in their factorization (plus perhaps some factor of $k$). Hence, $\gcd(x+1,n)\in\{p,q\}$.


How to perform file encryption using 128-bit AES

You are right to be confused, because you could just as well have asked "How can I encrypt a file using a CPU that supports xor, shifts and rotates?" The answer is that of course you can, but there is obviously a lot more to it, if you are going to do it right.

AES is just a standard block cipher primitive. The only thing this standard tells you, is how to transform a single 128 bit block using a key, into another 128 bit block. It doesn't tell you where the key is coming from, or how you are going to process any data larger than 128 bits. Those aspects have to be specified as well, and one example would be password based encryption as in PKCS#5 PBES2 with AES-CBC-128 combined with PBMAC1 with HMAC-SHA-256.

When reading the technical specifications of consumer software or business software, it is not that uncommon that the only thing specified is the block cipher primitive, such as "128 bit AES". In my experience this is often due to either of the following reasons:

The software developers don't have a clue about cryptography and are actually using AES-ECB-128 with a key that embedded as a constant in the software.
The software developers are using a proper file encryption scheme but specify only the block cipher primitive because that's the only buzz word that they thought was necessary for marketing reasons.
If the software is based on legacy software that used a scheme with e.g. 3DES, stating that they use "128 bit AES" might simply indicate that they use the same scheme as before, but have just substituted the block cipher primitive.

If you interested in how some existing software is encrypting files, just knowing that the software uses AES-128 is consequently not enough. If you are interested in which schemes and algorithms to look up if you were to write such software yourself, you have to be a lot more specific about your security requirements...

What's the relation between the person or entity encrypting the file and the person or entity decrypting the file?
Exactly what bad things do you hope to prevent by encrypting the file?


Is this DIY remote lock protocol secure?

Even after your updates, the first part seems unnecessary. However, steps 4-5 do indeed prevent the attacker from learning future nonces they could ask the key MAC values for. So the protocol steps 4-7 would be secure with a secure MAC.

I agree with CodesInChaos that using HMAC would be better, because H(m||k) has some weaknesses, while HMAC is standard. Unless you have a good reason to use MD5, I would also prefer to use a stronger hash, though HMAC-MD5 is still secure (that is about encrypted data, but applies generally).

However, I do not think the weaknesses actually apply here, since the attacker does not have freedom to choose the values they need to calculate the keyed hash for. So even as is it should be secure. Despite that I would recommend switching to HMAC. Even better would be to use an existing mutual authentication protocol meant for this purpose, like the one descrived in Chapter 10 of HAC (see 10.2.3).

The below applies to the protocol as described in the original version of the question.

  Key generates completely unique value that never repeats (some kind of a counter), let's call it "NONCE1".
  Key sends a request to the lock which consists of NONCE1 and H1 = MD5(NONCE1 + KEY1)
  Lock checks if H1 = MD5(NONCE1 + KEY1)

This part does not prove anything to anyone, so it is useless. An attacker who impersonates the key can reuse any previous nonce+MD5-pair because the lock does not know if the nonce is unique. An attacker who impersonates the lock can simply ignore the data received.

  Lock generates completely unique value that never repeats, let's call it "NONCE2".
  Lock sends a response to the key which consists of H2 = MD5(NONCE2 + KEY2)

Why not simply send NONCE2 to use as H2? The hash does not seem to help in any way, because the nonce is not used for anything else.

  Key does H3 = MD5(H2 + KEY3) and sends it back to the lock
  Lock checks if H3 = MD5(H2 + KEY3) and acts on that

This is the only part of the protocol that has a clear purpose: the lock is verifying an ad-hoc MAC to authenticate the key.


Solutions to Yao's Millionaire's Problem should suffice for this computation. In that setup, there are two parties each with an input. The output reveals whose input is larger, and nothing else.

So Alice and Bob just run the protocol with their respective inputs A and B.


Possibility of the encrypted text being the same as the supplied plain text!

For a fixed key, a block cipher is presumed to behave like a pseudo-random permutation (PRP) over messages.  What we are interested in is if the permutation contains a fixed point, i.e. if it is a derangement or not.  What we find is that there is about a 63% chance that there is at least one fixed point, and the expected number follows a Poisson distribution (i.e. there shouldn't be many).

Your argument about short messages doesn't apply to block ciphers used in practice, since they don't operate on messages smaller than a block.


RSA Timing Attack and Prevention through blinding

But how is the execution also dependent on the message (the inputs)?

Actually, there are (at least) two potential timing attacks.

One is as you suggest; the timing (at least, for this simple exponentiation algorithm) is related to the hamming weight of the secret exponents. However, as you have observed, the secret exponents aren't dependent on the ciphertext.

However, there is a second potential timing variation that the attacker might attempt to exploit.  Suppose that you compute an intermediate value $C^{k} \bmod N$, and that value just happens to be unusually small.  Then, depending on the bignum library you use, it is possible that the next operation (especially if it is square, possibly if it is a multiply) will go unexpectedly fast, and that timing variation would tell you if $k$ was an intermediate exponent (which gives you a number of bits of the secret exponent).

Now, in practice, it doesn't work that well; it's hard to compute $C$ values where $C^k \bmod N$ is small (and it becomes even harder if the implementation uses CRT, there you'd need values where $C^k \bmod p, q$ are small.

So, what you end up doing is passing in random $C$ values, looking for values that are processed unexpectedly fast, and deducing things from that.

  The proposed solution of Kocher is "blinding" by a adding a random value to the message.

I'm pretty sure you misunderstood.  For one, adding a random value to the message gives an unrelated result.

If Paul proposed anything (he has proposed a number of things; I don't remember hearing these specifically from him), he may have suggested one of the following two things:

Multiplying a random value to the message.  That is, select a random value $r$, compute $r^e \bmod n$ and $r^{-1} \bmod n$; then multiple $c' = (r^e \bmod n) \cdot c$; perform the RSA operation on $c'$ resulting in $t' = RSA_{private}(c')$, and then compute the final $t = t' \cdot (r^{-1} \bmod n)$.  The RSA operation is done on an equidistributed value, and hence there aren't any message-based side channel leaks there
Add a random value to the exponent.  That is, (and I'll assume you're doing CRT here) select a random value $r$, and compute $t_p = (c \bmod p)^{d_p + r(p-1)} \bmod p$ (and similarly for $q$).  Except for a couple of the lower order bits, the exponent you use are randomized (and that could be covered by always selecting $p \equiv q \equiv 3 \pmod 4$)

On the other hand, Paul would never suggest either of the above as the sole protection for a badly leaking modular exponentiation routine.  Using power analysis (invented by Paul), you could obtain the exponent from a single trace; this would foil either of these countermeasures.


Why does symmetric encryption require padding?

Symmetric crypto does not always have padding. Stream ciphers often will not require padding. Padding is necessary when using a cipher that requires plaintexts to be a multiple of a particular size. For example, AES in CBC mode requires plaintexts that are a multiple of 128 bits. So if your plaintext is not, you must pad to make it the right size.


RSA modulus (N) from public key and calculating N from p, q not equal


Is it possible to insert a key derivation function when using EAX?

As noted in archie's answer to your earlier question, the EAX paper first defines a generic encrypt-then-MAC composition method called EAX2, with separate keys for the encryption and MAC components, and proves its security (Appendix C).  It then defines EAX as EAX2 instantiated with CTR mode and OMAC, and with the same key used for both components, and then uses an additional result about OMAC (Appendix D) to prove that this composition remains secure even with the key reuse (Appendix E).

Anyway, what all this amounts to is that if you take EAX mode and modify it so that the OMAC key is independent from the CTR mode key, and make no other changes, then what you get is an instance of EAX2 (with CTR mode as the encryption method and OMAC as the PRF).  If you trust the proof that EAX is secure, then, by the same argument, you should also trust the sub-proof that shows EAX2 to be secure.

That said, there do exist some potential disadvantages to this change.  For example, even though the security proof of EAX2 is essentially a part of the security proof of EAX, that does not necessarily mean that authorities that have certified EAX to be secure necessarily accept EAX2 as certified as well.  Also, more practically, verifying the correctness of your implementation of EAX2 might be more difficult, since AFAIK there's no standard set of test vectors available for EAX2.

All in all, if at all possible, I'd recommend sticking with EAX and using an existing, known-to-be-good implementation of it.  However, if you do need to use generic encrypt-them-MAC composition with separately derived keys for regulatory or other reasons, EAX2 is a pretty good way to implement it.


For the purposes of your high school project, I suppose either one is fine. As you mentioned, one possibility is to convert the message to a bit-string using ASCII, and then interpret the bitstring as an integer and treat it as the message to be encrypted. If you need to "show your work" on paper or slides, then writing it in decimal is reasonable.

However, as @otus mentioned, this method is never used in practice nowadays because it falls short of what we require of modern cryptosystems, for various reasons. You can Google something like "textbook RSA" or "plain RSA" to find out more, and I would suggest that it would be a good idea to at least mention those issues in some way in your project.


Is the hash function defined in this exercise collision-resistant?

The padding scheme isn't collision resistant.

For any message $m$ where $|m| \not\equiv 0 \pmod n$, there will always be a collision between $m$ and $m || 0$.


All UDP information (including the port number) is encrypted:
https://tools.ietf.org/html/rfc1827#section-3

(Please note that the link above points to the specification of ESP as it was when Steven Bellovin published his USENIX paper. This RFC is now obsolete.)

Guessing the port number should be quite easy: use the netstat command to list UDP ports in use, ignore the ones with a peer address which does not match, and the ones used by known services.

Actually the answer could be found in the original paper a few lines bellow where the TCP case is discussed.

  Still, on modern high speed net works it isn't that hard to make the
  sequence numbers wrap, and the attacker may be able to learn the
  necessary port numbers by polling via netstat on either machine.

This is very simple: the attack does not require much sophistication on the attacker's part. All that is required is a network capture and basic knowledge of UNIX system utilities such as ps and netstat.

This is Bellovin's point here: in this case tampering of the transmitted data is not even necessary to mount an attack. This is why waiting for the end of the process is mentioned. The attacks which can be performed while the process is still running require more work or more specialized tools. (Bellovin's main attack involves tampering with unauthenticated CBC encrypted data, as pointed out by Poncho in a comment.)


I was wondering whether this encryption / decryption flow is very
  solid / secure.

What you have described is not an encryption scheme*, but a scheme for user authentication, that is a user tries to log-in, provides the password and you want to check if that password belongs to the given user.

Now what you have described will probably achieve that goal, but it's not the kind of approach that is really "considered" good for this use-case in cryptography:

The length of passwords is limited by the cipher's keysize (eg 32 bytes?).
Ciphers are not designed to provide good security with non-uniformly distributed keys.
This approach will require quite low storage and will be very fast to verify meaning an attacker can just ask eg a GPU to run through billions of possible passwords per second.

But on the plus-side, using the password as a key on a fixed message is kind of a hash function and using the IV / the prefix / the suffix kind of is a salt, which are both central ingredients for password hashing.

Now what you actually want here is a password hashing scheme (PHS). That is a function that takes a salt, that you store in your database, a cost parameter (set) and a password and outputs a value deterministic in these parameters that you can check against a pre-stored value in your database. You would then generate a unique salt for each user and use the highest cost parameter in terms of time and memory that you can tolerate to slow down attackers for the case when your database leaks. Common PHSs are Argon2, bcrypt, scrypt or if you're out of options PBKDF2.

*: An encryption scheme would specify, given a key, a nonce and a message how to generate an encrypted message.


Are the weaknesses of my s-boxes attackable?

The strengths and weaknesses of an S-Box can be determined by analysis of the commonly agreed within the cryptanalytic community S-Box properties.
The following list of properties have been described in a 2014 paper "Study of S-box properties in block cipher" by Kamsiah Mohamed and colleagues: Robustness, Balancing, Strict Avalance Criterion, Nonlinearity, Differential Uniformity, Linear Approximation, Algebraic Complexity, Fp/OFp, Bit Independence criterion. There may be other important properties as well.
Practical aspects of strong S-Box generation, considering these properties, have been described by Waqar Ahmad Khan and colleagues in a 2011 article "Construction of Cryptographically Strong 8x8 S-boxes".
A toolbox for S-Box analysis have been described by Stjepan Picek and colleagues in a 2016 paper.
Your question was whether we can find a way to attack the encryption scheme based on your S-Boxes, but from the description that you gave, on how you use them, they are not actually S-Boxes, but the keys. In cryptography, the S-box (substitution box) is the basic component of the symmetric key algorithm that performs replacement. In block ciphers, S-Boxes are usually applied to conceal the relationship between the key and the ciphertext to satisfy the Shannon's property of confusion. This property refers to making the relationship between ciphertext and symmetric key as complicated and involved as possible. S-boxes need to be strong, in terms of the properties above mentioned, but they are not necessarily need to be secret. To the contrary, in a Russian GOST 28147-89 (RFC 5830), developed in the 1970s, S-Boxes are secret, and are called "long-term" keys, in addition to "session" keys, so both "long-term" and "session" keys comprise the key. This approach has its drawbacks because the "long-term" key, i.e. the S-Box should be thoroughly analyzed to comply to the properties above mentioned. What you call "S-Box" in your algorithm is actually a key. If what you call "S-Box" is actually a one-time pad, i.e. a truly random key used only once, then it is a completely different matter. The one-time pad was first described by Frank Miller in 1882 and was reinvented in 1917 by Gilbert Vernam who in 1919 was granted an US Patent 1,310,719 for the encrypted XOR operation of one-time pads. So, if what you call "S-Boxes" fit the definition of one-time pads, than you've got the perfect secrecy. But this is unlikely that you meant that. Thus, I would recommend to analyze your S-Boxes according to the properties above described.


I suppose this is a terminology question. "A digital signature scheme which can sign many documents with one private key" means something like this:

There are some sets $M$ (the "message space", often the set of bitstrings of any length, or some useful subset thereof), $K_{pub}$, $K_{priv}$ (the public and private "key spaces") and $S$ (the signature space).
There is a tuple of (probabilistic and efficiently computable) functions $(g, s, v)$.
$g : \varnothing \to K_{pub} \times K_{priv}$ ($g$ generates a random key pair).
$s : M \times K_{priv} \to S$ ($s$ signs a message, i.e. generates a signature from the private key and message)
$v : M \times K_{pub} \times S \to \{\mathsf{true}, \mathsf{false}\}$ ($v$ verifies a signature)
If $(y, x) = g()$ and $m \in M$, then $v(m, y, s(m, x)) = \mathsf{true}$ (or at least with overwhelming probability).

Normally we also want that the scheme is secure, which then adds some more properties:

Given $y$ (the public key) and a message $m$, without knowledge of $x$ it is hard to create a $\sigma \in S$ such that $v(m, y, \sigma) = \mathsf{true}$, even if some (or even many) other $(m', \sigma')$ are known, or even signatures to other messages can be requested. (This is known as "universal forgery".)
It should even be hard to create any message $m \in M$ and $\sigma \in S$ such that $v(m, y, \sigma) = \mathsf{true}$ (other than the $m'$s which were given/queried as examples). (This is known as "existential forgery".)

(There are also variants of this definition where the number of documents which can be signed with each key before the security gets lost is limited, but these obviously are not "signature schemes which can sign many documents with one key".)

Usually there also is some formalization of "hard", often with a security parameter.

Similarly, we have the term of "hash function", something like that:

There is a message space $M$ (usually the set of bitstrings of any length, or some useful subset thereof) and a hash space $H$ (usually the set of bitstrings of some fixed length).
There is a function $h : M \to H$.

The "collision resistance" property then is something like

It is hard to find $m_1, m_2 \in M$ with $h(m_1) = h(m_2)$.

The "there exists a digital signature scheme which ..." in the quoted lecture extract supposedly means as much as "there exists a secure signature scheme which ...".

We already know that there are signature schemes (RSA, DSA, ECDSA, ...), but it is not proven if they are actually secure. (We sure hope so, and nobody did break them publicly yet, but it might not actually be possible to prove anything, or it might be that there is no secure signature scheme at all.)

We also don't know if there exist any actually collision-resistant hash function. We have some candidates (like SHA-2), and some previous candidates which proved to actually be not collision resistant (MD4, MD5).

The argument then is:

If there is any secure signature scheme (for multiple documents with each key), then there has to be a collision-resistant hash function.

(The idea is that you actually can use the signature scheme as a hash function by using a fixed key, and the signature scheme is not secure if you can find two messages with the same signature (i.e. a hash collision). I think this doesn't actually follow from my security properties mentioned above, so maybe your lecture used some other security definition.)
Also there will be shown (in the following paragraphs/pages of your text) that from any collision-resistant hash function you can build a secure hash-based signature scheme.
So it follows: If there is any secure signature scheme (which can sign many messages) at all, then there is a secure hash based signature scheme.


Which symmetric encryption systems, pseudorandom number generators, and hash functions are best suited for reversible computers?

We can think of encryption as a deterministic function producing ciphertext $C$ from key $K$, plaintext $P$, and for other than deterministic encryption an extra input $R$ for randomness/Initialization Vector. That function $(K,R,P)\mapsto C$ can't be both secure and reversible. Proof: it would be possible to obtain $(K,R,P)$ from $C$ because of reversibility, and from that extract $P$, which goes straight against the security goal.

The same reasoning shows that a fully reversible TRNG can't be secure, or a fully reversible hash function first-preimage resistant.

However, we can implement all steps reversibly, except discarding some of the final result. In particular, for any size-preserving symmetric cipher, in principle we can reversibly implement $(K,R,P)\mapsto(G,C)$, with garbage $G$ the same width as $K$ (and $C$ the same width as $R$ and $P$ combined), and discard $G$ from the output. For a block cipher, that is $(K,P)\mapsto(G,C)$ (proof and/or straightening welcome; Scott Aaronson, Daniel Grier, Luke Schaeffer's The Classification of Reversible Bit Operations would be a useful reference).

With that conception of reversible cipher allowing to discard garbage the width of the key, I tentatively answer:

Yes, if your AES-128 replacement with easy implementation as Toffoli-like gates qualifies.
Yes. The AES block cipher is a well-studied example, and all its standard modes qualify. For the reversible construction of AES-128, see

Kamalika Datta, Vishal Shrivastav, Indranil Sengupta, Hafizur Rahaman's Reversible Logic Implementation of AES Algorithm, in proceedings of DTIS 2013. My reading is that it reports implementing $(K,P)\mapsto(G,C)$ for AES-128 using less than $2^{17}$ Toffoli gates.
Markus Grassl, Brandon Langenberg, Martin Roetteler, Rainer Steinwandt's Applying Grover’s Algorithm to AES: Quantum Resource Estimates, in proceedings of PQCrypto 2016, seem just over $2^{20}$ Toffoli gates using a different approach.

Rather no. Making things easily reversible when they are not would be a huge design change, likely to compromise security. That applies in particular to Feistel block ciphers using large non-reversible round functions, which I guess are quite hard to re-express as reversible.

I asked how costly DES would be.


Would it be possible to create a game where one would need to decrypt a simple encryption?

Caesar cipher? Its a simple substitution cipher where you can solve with just a pen and paper.

Encryption is done by shifting each plaintext letter, x by n places the alphabet or mathematically, ENCRYPT(x) = (x + n) mod 26. Similarly, the decryption will be the reverse, DECRYPT(x) = (x - n) mod 26. (see wiki http://en.wikipedia.org/wiki/Caesar_cipher#Example)

So, you get a friend to pick a random n and compute the encryption for a randomly chosen four letter string (using free online calculators like http://online-calculators.appspot.com/caesar_ext/). You should not know both n and the plaintext. But the plaintext should be some english word or equivalent in order for it to make sense when you decrypt.

Then, you start the decryption process by trying out all possible values of n until the decrypted plaintext is make sense. If your first two/three decrypted alphabets is not an valid word, that means your chosen n value is wrong and you should try another n.


Change in probability of collision when removing digits from MD5 hexadecimal hash values

First things first: there is nothing magical in hexadecimal. The output of MD5 is, nominally, a sequence of 128 bits, or, if you prefer, 16 bytes (each being able to get any value between 0 and 255). Hexadecimal is just a trick to represent a single byte as two characters in a limited range (digits, and letters from 'a' to 'f'). If you can have 30 characters then you can probably use more than the hexadecimal digits. For instance, with Base64 encoding, you can unambiguously represent any MD5 output (16 bytes) into 24 characters chosen in a list consisting of digits, uppercase letters, lowercase letters, '+', '/' and '=' (the '=' sign appears only at the end, and your 24 characters will always end with a pair of '=' signs, which you can altogether omit; hence, make that 22 characters).

To answer your initial question, assuming that MD5 behaves "randomly" (which is kind of true as long as nobody is actively trying to produce collisions), then keeping $n$ hexadecimal characters means keeping $4n$ MD5 output bits, and collisions are expected to appear around $2^{2n}$ keys. With $n = 30$, that's $2^{60}$, also known as "approximately a billion billions", which is still kind of huge. Still, you'd better use a shorter encoding such as Base64, which avoids the issue altogether.


Issues with Seeding Random Number Generator Using Password

I'm still not entirely sure what you're asking but you can use password authenticated key agreement (PAKE). It will prevent off-line brute-forcing of the password.


Would this method allow fast authenticated encryption using only a single encryption operation per block?

This does not meaningfully authenticate the ciphertext. Your encryption is the same as OFB, meaning no block depends on the previous plaintext; for instance, $$C_2=P_2\oplus E(P_1\oplus (P_1\oplus E(IV\oplus 0)))=P_2\oplus E(E(IV)).$$ That means confidentiality should be fine; however, it provides no authentication except of the length of the message.


Is the $\ell$-Diffie Hellman Inversion easy when g is known?

No.

The stated $l$-DHI problem is believed to remain hard when $g$ is known.

Actually, in the quoted page, it is assumed that $g$ is known throughout. This is obvious in particular in the sections on DLP and CDH.


AES in CBC Mode Is totally unsecure if no defense is provided for padding oracle attack, right?

The cryptographic community moves very slowly. Take MD5 security for example. A design flaw was first published in 1996 and a collision (with more design flaws) found in 2004. Yet in 2012, authors of the Flame malware were able to use an MD5 collision to forge a Windows code-signing certificate. And we still hear of password-hash dumps that use MD5 today.

  how can it be that AES256CBC is often touted as strong modern encryption without mentioning that implementations lacking proper HMAC validation (Encrypt-Then-MAC), or some other padding oracle defense, are actually not secure at all?

This is definitely the way the community is going. I haven't done the analysis, but I'd guess that most TLS/SSL connections these days are using integrity protection (either HMAC or an AEAD mode). Integrity protection is one of the first things that gets mentioned to people on Crypto.SE too when they propose something that doesn't use it.

Something to remember is that padding-oracle attack is an online attack and very noisy. So there are a lot of use cases of cryptography where it simply does not apply. I agree with your sentiment, however. Authenticated encryption should be the default. We are getting there, but it is taking time.


how to calculate the non linearity of each element of s box?

The answer to How does one practically calculate the non-linearity of a multi-output boolean function like the AES s-box? describes explicitly how to do this both for single output bits and the whole output vector of the sbox.

If you have the ANF of an sbox output bit, you can obtain its hadamard transform from there by using the mobius transform. See my answer to the question
Generate ANF from SBox for information on the mobius transform.

The weight of the lowest weight nonzero hadamard coefficient is equal to the nonlinearity.


Math to replace s-boxes - Good or bad idea?

The S-boxes in quite many encryption algorithms (for example, in AES) have been already built with math (the AES S-box is an inversion function in $GF(256)$ plus an affine transformation). The lookup tables exist solely to ease the implementation. In fact, modern Intel/AMD CPU are already equipped with AES round function instructions, so the tables are not needed at all.

When people design new S-boxes, the first question to answer is Why? and the next one is What properties do they have compared to the existing ones?. Until there are reasonable answers, the proposals are not used and even not being analyzed.


What are the risks of using CTR mode with 64 bit blocks?

I believe that he was referring to the misconception that the birthday problem that arises in encryption is only when you use the same counter twice. If a random IV is used, then such a counter repeats at $2^{32}$ blocks with high probability (and if you want a $2^{-32}$ safety margin then you can only encrypt $2^{16}$ blocks). However, if distinct counters are guaranteed to be used, then you never get a collision on the input to the block cipher and so you can encrypt more. I assume that the NSA claim was with reference to this version of counter mode where distinct counters are guaranteed (something that's easy to do if you have state).

Anyway, this is a misconception for the exact reason that you point out. The problem is that people think that this leaks only a very little bit of information, unlike in CBC mode where a collision in the ciphertext immediately reveals the XOR of two plaintext blocks. Recently, at EUROCRYPT 2018, a paper was presented showing how to obtain actual plaintext in a number of realistic scenarios when counter mode is used beyond the birthday bound, even with unique counters. The paper is called The Missing Difference Problem, and its Applications to Counter Mode Encryption. I recommend reading it.


What is the notion of an interactive assumption?

You can define most hardness assumptions in terms of a game played with an adversary. See Shoup & Bellare-Rogaway for details.
Example: You can define DDH assumption in terms of the following game:

Challenger picks a random bit $\beta$; and random $a,b,c \gets \mathbb{Z}_p$. He computes $A = g^a; B=b^b$ and $C = \begin{cases}g^{ab} & \mbox{if }\beta =0 \\ g^c& \mbox{if } \beta=1\end{cases}$ and sends $A,B,C$ to the adversary.

Adversary tries to guess $\beta$.

Example: You can define CPA-secure (public-key) encryption in terms of the following game:

Challenger generates keypair $(sk,pk)$ and gives $pk$ to the adversary.

Adversary chooses two plaintexts $m_0, m_1$.

Challenger chooses random bit $\beta$ and gives $\textsf{Enc}(pk,m_\beta)$ to the adversary.

Adversary tries to guess $\beta$.

The first game is non-interactive, with the adversary simply receiving values (the final guess of the adversary is not really counted). So DDH is a non-interactive assumption.
The second game is interactive since the adversary is allowed to choose his plaintexts after seeing the public key. So CPA security is an interactive assumption.
Now suppose you're trying to prove that some interactive system of yours is secure. You can always just take "my system is secure" as an assumption, but you haven't actually done anything in this case. On the other hand, if you base the security of your interactive system on a non-interactive assumption, then you must have actually done something non-trivial. In general, we want to base security on the simplest possible assumptions, and interaction is a natural way to measure the "simplicity" of an assumption.

Victor Shoup. Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive, Report 2004/332, 2004.
Mihir Bellare and Phillip Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In EUROCRYPT 2006, LNCS vol 4004, p409-426.


The different charsets are simply the result of different encodings. A secure random number generator will generate a sequence of bits indistinguishable from pure random. These bits can then be encoded in several ways. In your case the SecureRandom.hex is returning base64 encoded bits, while OpenSSL::Cipher::Cipher.new("aes-256-gcm").random_key is returning ASCII encoded bits (where bit sequences that have no ASCII representation are prefixed with \x and hex encoded).

These two methods do not, in fact, return the same number of random bits:

In [7]: from binascii import a2b_base64

In [8]: openssl = b'\x1A\xAC\x8F\xC4mX\xAE\xDE\x04\xE1\x83\x8F\xFF^\x8C3KJ\xBE\vt\xE4\xBC\x14B\xDEro\xB8\xF5Yy'

In [9]: len(openssl)
Out[9]: 32

In [10]: secrand = a2b_base64('Z6sBQRGKll7FEKz3ebfUiGupwhPS3QVm')

In [11]: len(secrand)
Out[11]: 24

As you can see, SecureRandom.hex generates 24 bytes = 192 bits, and OpenSSL::Cipher::Cipher.new("aes-256-gcm").random_key generates 32 bytes = 256 bits.

Since AES-256-GCM requires a 256 bit key I recommend using OpenSSL::Cipher::Cipher.new("aes-256-gcm").random_key.

EDIT

Since the value SecureRandom.hex returns in the question was updated to be a hexidecimal encoding the amount of random bits it generates is no longer 192. It actually generates less random bits now, since a base64 encoded string can encode more bits than an equally long hex encoded string.

In [1]: from binascii import unhexlify

In [2]: k = unhexlify('3d499a7b8f57773281ca2d47698a0062')

In [3]: len(k)
Out[3]: 16

So now we have 16 bytes = 128 bits.

In general, assuming a secure random number generator, the number of bytes of entropy that an encoded string of length $n$ has is:

ASCII - $n$
base64 - $\frac{3n}{4}$
hex - $\frac{n}{2}$
binary - $\frac{n}{8}$

You can multiply any of those terms by 8 to get the equivalent values in bits rather than bytes.


Is the risk of a collision for OCB mode mitigated by upping the block size of the cipher?

Using a larger blocksize in a cipher will always aid in mitigating collisions.

For a practical example, take what OWASP says about key management:

  If the amount of data encrypted grows beyond a certain threshold, a new key should be used. This certain threshold varies depending on the encryption algorithm used, but is typically 235 bytes (~34 gigabytes) for 64 bit block ciphers (DES, 3DES, Blowfish, RC5, ...) and 268 bytes (~ 295,147,905 terabytes) for 128 bit block ciphers (AES, TwoFish, Serpent). If encrypting with a modern cipher, this threshold is unlikely to be reached, but it should be considered when evaluating algorithms and rotation procedures.*

I think Niels' views on the use of OCB are more academic than most people who might implement such a system. The biggest reason why OCB isn't being used is because of its patent. It also didn't help that in OCBv1 it didn't allow additional authenticated data. It was later added in OCBv2, but it did hurt adoption.

To reiterate on the above, Niels presents a more academic and logical argument against the adoption of OCB, but the biggest reason why it wasn't adopted was due to the patent the author has on it.

*https://www.owasp.org/index.php/Cryptographic_Storage_Cheat_Sheet#Rule_-_Limit_quantity_of_data_encrypted_with_one_key


For a featureless identifier a simple random number + MAC thereof should work.

You don't actually need encryption because your number doesn't contain any sensitive information and checking the MAC allows you to verify that this is actually a token that you generated.

This requires only a symmetric key for MACing on the server.


Winternitz hash based signature signing and verification

How is signature $\sigma$ computed?

Well, you left a few steps out of your signing steps:

Signing steps

Compute digest of message $d = g(M)$
Prepend minimum number of zero's to make length of $d$ divisible by $w$

(Note: in practice, the length of $d$ is typically already divisible by $w$, and so this step usually doesn't do anything; in any case, $d$ will be $t_1$ digits long after this step)

Generate an "inverse checksum" of $d$; that is, treat $d$ as $t_1$ digits of length $w$ each $d_0, d_1, ..., d_{t_1 - 1}$, compute $k - \Sigma\  d_i$ for some constant $k \ge t_1 (w-1)$, and express that as the $t_2$ digits $d_{t_1}, d_{t_1 + 1 }, ..., d_{t_1 + t_2 -1}$

For each $d_i$, take $x_i$ and apply $f$ to it $d_i$ times

The result of these operations on the $t_1 + t_2$ digits are concatenated; that's your signature

You asked for an example, here's a toy one; let us assume that $w=2$ and $n = 4$.  Then:

We have $t_1 = 2$ and $t_2 = 2$

We compute $g(M)$ as 0111, which is $\{ 1, 3 \}$ as expressed as $w$-bit digits

We don't need to prepend any zeros, the length of $d$ is already a multiple of $w$

We generate our inverse checksum; we have $d_0 = 1$ and $d_1 = 3$; we'll use the minimal $k = 6$, and so we have $k - \Sigma \ d_i = 2$, which we'll encode as $d_2 = 0$ and $d_3 = 2$

We compute the Winternitz chain for $d_0$; $d_0 = 1$, and so this is $f(x_0)$; that's the first 2 bits of the signature.

We compute the Winternitz chain for $d_1$; $d_1 = 3$, and so this is $f(f(f(x_1)))$; that's the second 2 bits of the signature.

We compute the Winternitz chain for $d_2$; $d_2 = 0$, and so this is $x_2$ (that is, for digits of 0, we give out the private key value); that's the third 2 bits of the signature.

We compute the Winternitz chain for $d_3$; $d_3 = 2$, and so this is $f(f(x_3))$; that's the last 2 bits of the signature.

Why there is two functions $f$ and $g$, is there can be only one hashing function. What is the role of function $f$?

They, of course, perform different roles; $g$ hashes an arbitrary message down to $n$ bits; while $f$ is a one-way function that is used within the Winternitz chain itself.  They are usually (but not always) based on the same hash function; however how the hash function is used is typically optimized for each role separately.

Of course, in practice, we do a few refinements of the above scheme:

We actually use a different $f$ function for every iteration, and for every digit; that's to avoid multi-target attacks

Our public key really isn't $(t_1 + t_2)n$ bits long; typically, there's a final step that combines them into a single $n$ bit value.

Knowledge of these refinements is not necessary to understand Winternitz signatures; however you ought to be aware of them if you dig into a real usage.


Question on PKCS11 2.40 spec and AES_CBC wrap

if any key has NULL bytes (or zeros) at the end, how the unwrap knows how many padded bytes are added?

PKCS#11 doesn't unpad unless you indicate PKCS#7 padding using _PAD. Decryption will just leave all the zero bytes. This is not a problem if you either know the size in advance, or if you've padded it yourself using a scheme that is compatible with the zero padding such as PKCS#7 compatible padding. PKCS#11's zero padding operation doesn't pad if the input is already a multiple of the block size, after all.

Also, I'm the beginner for cryptography so I'm not sure whether any secret key can end up with zeros or not. Please clarify me this also.

It can, but if you unwrap then the key size of any wrapped secret key is generally known in advance, so it shouldn't matter. You will have to provide the key size yourself in the template during unwrapping (if you use ECB or CBC without _PAD option). To quote the information in the mechanism page of PKCS#11 v2.40, section 2.8.5 AES-CBC:

For wrapping, the mechanism encrypts the value of the CKA_VALUE attribute of the key that is wrapped, padded on the trailing end with up to block size minus one null bytes so that the resulting length is a multiple of the block size. The output data is the same length as the padded input data. It does not wrap the key type, key length, or any other information about the key; the application must convey these separately.
For unwrapping, the mechanism decrypts the wrapped key, and truncates the result according to the CKA_KEY_TYPE attribute of the template and, if it has one, and the key type supports it, the CKA_VALUE_LEN attribute of the template.  The mechanism contributes the result as the CKA_VALUE attribute of the new key; other attributes required by the key type must be specified in the template.

(emphasis mine)
Private keys commonly use ASN.1/DER encoding, so if you wrap those you can calculate the size of the key using the first length field of the initial TLV value. Then you - or the token - can remove the spurious zero valued bytes.

Generally I'd avoid wrapping AES-192 keys, they are just a nuisance as the key size is not a multiple of the block size.
Moreover, I'd be extremely cautious when it comes to (asymmetric) private keys. Many tokens will happily use ECB or zero-IV CBC to encrypt private keys, and that may actually leak information about those wrapped private keys.
PKCS#11 is an old standard, and many of the careless decisions made at the beginning are likely to perpetuate far into the future.


How to prove the security of block ciphers

There is actually a field of study regarding provably secure block ciphers.  The seminal paper was "How to construct pseudorandom permutations from pseudorandom functions" (1988) by Luby and Rackoff.  Their paper used pseudorandom round functions in a Feistel construction, and proved that 4 rounds were sufficient to make the resulting block cipher a pseudorandom permutation against chosen plaintext and ciphertext attacks.  That paper spawned a cottage industry of similar papers based around the Feistel construction, or generalizations thereof.  In addition to academic papers and theoretical cipher constructions, this also inspired a few actual concrete block ciphers, such as the BEAR and LION ciphers by Anderson and Biham that Marcellus mentioned, and the Turtle block cipher, by Matt Blaze, for which the author claims that "recovery of its internal state given its inputs and outputs in NP-complete."

More recently, a similar wave of papers have developed regarding provably secure "key alternating" block ciphers, which are like AES in that the round function consists of the entire state being xored with a key, followed by an unkeyed permutation.  The seminal paper for this wave was
"A Construction of a Cipher From a Single Pseudorandom Permutation" (1991) by Even and Mansour, which focused on the security of a key alternating block cipher with a single round.  This was then expanded to iterated constructions with multiple rounds in "Tight Security Bounds for Key-Alternating Ciphers" (2013) by Chen and Steinberger, inspiring a similar cottage industry of related papers in recent years.

But the overwhelming majority of actual, concrete block ciphers are not provably secure in the sense of the above literature.  Instead, they accumulate confidence over time insofar as they continually resist cryptanalytical efforts.  As Biv described, they may also attempt to prove immunity to certain specific kinds of known attack; whereas the academic papers above purport to prove security against all attacks, known and unknown.


Digital sign HTML form data before sending it to server?

Is it the good approach?

No, it is not. You say you want to do this for legal reasons. If your server knows the private key (as it does in this case), the server or anyone with access to the server will also have access to the private key and can therefore sign any form they want. Therefore, your proposal does not meet your goals.


No, not as described in the question.

Putting aside the block size confusion that Richie Frame mentions in a comment (AES block size is always 128), there is no advantage to encrypting a second half of an IV in GCM mode in particular, and rarely in other modes.

In GCM mode the actual IV is used to derive a nonce for CTR mode encryption. By adding a block of data in front of the message you only shift the message forward by one block. An attacker can just ignore that block in any attacks they might have on the encryption layer. The extra block also affects authentication, but it should not make the attacker's job any harder since GCM authenticates the ciphertext, which just becomes longer.

Note that GCM actually allows arbitrary length IVs directly. There is, however, not really a benefit to using an IV longer than 128 bits unless it is more convenient for the application in question (it is hashed down to 128 bits anyway). In fact, 96-bit nonces are most efficient (avoiding the hashing step), if you can make sure they are unique.

With e.g. CBC mode the encryption of later blocks depends on the plaintext, so it may seem like encrypting a random block would help. However, the attacker is still faced with an equally difficult problem as the first block of ciphertext effectively becomes the IV: $IV' = E_k(IV_1 \oplus IV_2)$. Here there is some advantage, since predictable (but unique) $IV_1 \oplus IV_2$ would result in an unpredictable $IV'$, and CBC requires unpredictable IVs. However, it would be better to just use an encrypted counter if you do not have a good source of random IVs.


I don't know of any chat protocol that would use this approach.

I get it from your question that once the symmetric key is established, Alice and Bob communicate directly using it and that it is not an issue that the server, if malicious, can defeat any security achieved by this.

However, it appears to me that your protocol suffers from a major problem, namely the fact that the server itself is not authenticated in any way. That means that an adversary with control of the network could impersonate the server, which by design knows the secret symmetric key Alice and Bob would be using.

Alice and Bob also never authenticate each other and rely on the lower layer and the supposingly secure shared key to communicate, so they may be impersonated very easily in such a scenario.


How can I get select messages ciphers for salsa20poly1305 for unit tests?

Just use the test vector specified by DJB himself, specified here, chapter 4 (just XSalsa20) and chapter 10 for the box. This will already test all your primitives.

To perform boundary tests, I would strongly suggest you first document the boundaries. These are the places where there is a difference in e.g. buffer handling for the MAC function. If you test those boundaries against your own library then the MAC will still generate the same wrong value.

There seems to be TweetNaCl.js available online, so you can generate your own vectors after establishing your boundaries.


Can you break a Vigenere cipher with key length of 2 and message/cipher text length of 4?

If I can prove there's no single key that can encrypt to both outputs I can prove with 100% certainty which message it is, but if not I can't.

"pqrs" or "jmlo"

You can identify which password it is by comparing each letter with the corresponding letter once encrypted. For example, compare $P-R$ with $J-L$ (treating each letter as a number

They look like variables in this notation but they're not.

P and R are 2 letters apart; J and L are also 2 letters apart so that's inconclusive.
Q and S are 2 letters apart. M and O are also 2 letters apart; so that's also inconclusive.

This means there exists a 2-character key mapping each password to the same ciphertext (the mathematical relations between the letters are insufficient to distinguish). As such, there's no way in this case to identify which password it is.


How Elliptic-Curve affects the Server Key Exchange parameters

Generally a pre-selected set of parameters are used: a named curve such as brainpoolP256r1. Here the parameters have been pre-selected. It is computationally inefficient to choose the EC domain parameters on the fly, and preferably the other party should be able to make sure that the parameters are generated securely. So the $p$ and $g$ used for Finite Field DH are commonly replaced by a single identifier (e.g. in text or an OID, depending on the implementation) that represent the domain parameters.

The the curve parameters can also be communicated using the actual values. For a curve over a prime field the parameters are:

the prime field $p$;
the coefficients $A$ and $B$;
the base point $G$ consisting of coordinates $x$ and $y$;
the prime order $q$;
the cofactor $h$, commonly set to 1.

sometimes a seed - to generate the parameters - is communicated as well.

The base point G here takes the same role as the $g$ in Diffie-Hellman over a finite field. Instead of repeating the answer, you can find a complete description here.

In general ECDH is described using point multiplication instead of exponentiation.

Lets describe it using:

$P$ for the public key (so $P_A$ is the public key of $A$)
$S$ for the private key (so $S_A$ is the private key of $A$ called $a$ in the question)
$X$ is the shared secret as we're running out of variable names
${}\times{}$ is point multiplication

Calculation of the public key:

FFDH: $P_A = g^{S_A}$
ECDH: $P_A = S_A \times G$

And the key agreement itself:

FFDH: $X_B = P_A^{S_B} \to X_B = (g^{S_A})^{S_B} \to X_B = g^{S_AS_B}$
ECDH: $X_B = S_B \times P_A \to X_B = S_B \times (S_A \times G) \to X_B = S_A \times S_B \times G$

and for both you can see that they rely on the commutative properties of modular exponentiation and point multiplication. It is easy to see that $X_A = X_B$ using both methods.

It is simply possible to write $g^a$ and say that the normal exponentiation function is representing multiplication in a cyclic group. So in that case $g^a$ would be seen as $g \times a$ for Elliptic curves. $g$ is however generally written in uppercase as $G$ (not to be confused with cyclic group $G$) because it is a point, not just a single number.

Although EC operations are often described using multiplication and (point) addition it is important to keep reminding yourself in which model you're operating. There are a lot of ways and a lot of ways to map variables in ECC, making a hard to understand field even more difficult to grasp.

In the end your CPU will still have to perform modular exponentiation to implement point multiplication. The modular exponentiation is however over smaller numbers, making it more efficient.


Verification of Pinocchio (verifiable computation)

$y$ is the values of the output wires, so it is used to compute $g_v^{v_{io}(s)}$, $g_w^{w_{io}(s)}$, and $g_y^{y_{io}(s)}$. (Remember that $c_k$ is the value of the wire with index $k$.)


This [Carter-Wegman] MAC is not, in general, secure in the quantum setting

This is true; however we need to ask "what is this setting, and is it a realistic one?"

This setting is one where the adversary can ask queries that are composed of a superposition of quantum states, and the oracle returns the superposition of the answers.  In other words, the oracle (that is, the device with the MAC key that computes the MAC) must compute the answer without any decoherence in the quantum state, and the messages to and from the adversary must also not have any decoherence.  As far as we know, any significant amount of computation without decoherence must be done using Quantum Error Correction (to adjust for the decoherence that just occurs naturally), this effectively means that the device with the MAC key must be a part of the quantum computer (but, for some reason, the attacker doesn't look inside the device and just extract the MAC key).

I would argue that this is not an attack model that we need to worry about, if we're just creating devices that exchange messages, and are worried about someone building a Quantum Computer.

We do need to worry about Grover's algorithm, which given a function $F(x)$ with an unknown $n$-bit input, find an $x$ where $F(x)$ is a specific value in $O(2^{n/2})$ time.  However, the attacker can't take advantage to try to compute a 128-bit MAC tag; because, in addition to the tag that the attacker is searching for, the algorithm also has the key as the input, and the attacker doesn't know that.  Grover's algorithm could be used to attack the key itself; we can prevent that from being a possibility by using a 256 bit key.


In this answer, I am reducing using that centered representation of $\mathbb{Z}_q$ and $\mathbb{Z}_w$. Also, I am writing $\ell$ instead of $l_{w,q}$ to simplify the notation.

Concrete examples:

$Dec_{w,q}(a) = (6x^2 - 8x - 3, 4x^2 + 4x + 3)$
$Pow_{w,q} = (61x + 31, 61\cdot16x + 31\cdot16) = (61x + 31, -19 x + 98) \pmod q $

Therefore, we have the following dot product:

$$\begin{align}
Dec_{w,q}(a)\cdot Pow_{w,q}(b) &= (6x^2 - 8x - 3) \cdot (61x + 31)+( 4x^2 + 4x + 3) \cdot  (-19 x + 98) \\
                 &= (366 x^3-302 x^2-431 x-93) + (-76x^3+316 x^2+335 x+294)\\
                 &= 290 x^3+14 x^2-96 x+201 \\
                 &= 91x^3 + 14x^2  -96x + 2
\end{align}$$

And the usual product reduced modulo $q$ is:

$a \cdot b = 4270 x^3+5586 x^2+ 4481x+1395 = 91x^3 + 14x^2 + -96x + 2$

Explanation:

In order to have a simple understanding, think of the integers (or, polynomials with degree equal to zero): in this case, it is easy to see that given an integer $a$, we can write $a$ in base $w$ obtaining digits $a_\ell, ..., a_1, a_0$ such that

$$a = \sum_{i=0}^\ell a_i \cdot w^i$$

In particular, if $w = 2$, then this is the binary representation.

The key point now is to understand why it is still valid if $a$ is any polynomial. In fact, it is valid because we just write each coefficient in base $w$, obtaining $\ell$ digits for each coefficient and then we define $\ell$ polynomials, with each polynomial $a_i$ having the $i$-th digits of each coefficient...

For instance, let $p(x) = 3x^3 + 2x + 1$, $q = 199$ and $w = 2$, then, write each coefficient in base $w$, obtaining $3 = (1,1)_w$, $2 = (0,1)_w$, and $1 = (1, 0)_w$, thus, we got
$$Dec_{w,q}(p) = (\underbrace{1x^3 + 0x + 1}_{\text{First digits}}, \underbrace{1x^3 + 1x + 0}_{\text{Second digits}})$$

So, once we have accepted that the summation above holds for any polynomial $a$, i.e., we can decompose any polynomial writing its coefficients in base $w$, then, understanding why the dot product is equal to the usual product is straightforward.

The function $Pow_{w,q}(b)$ just put the exponents of the decomposition of  the summation above in a vector with the polynomial $b$: $Pow_{w,q}(b) = (b\cdot w^0, b\cdot w^1, ..., b\cdot w^\ell)$.

Therefore, we have

$$
\begin{align}
Dec_{w,q}(a) \cdot Pow_{w,q}(b) &= (a_0, ..., a_\ell) (b\cdot w^0, ..., b\cdot w^\ell) & \\
 &= \sum_{i=0}^\ell a_i b w^i & (\text{By defn. of dot product}) \\
 &= b \sum_{i=0}^\ell a_i  w^i & (\text{Since } b \text{ doesn't depend on } i)\\
&= b a  & (\text{With the above equality})
\end{align}
$$

About your other issue:

  why it is better than school-book polynomial multiplication followed
  by modular reduction.

I think you have miss understood SEAL's manual... Those two functions are used in the relinearization step (called KeySwitch on the original paper), and they are not used to increase the efficiency of the multiplication, they are used to guarantee the correctness of the decryption under the original private key (and also to manage the noise growth). I suggest that you read section 5 of the original YASHE paper.


The ability to recover $x$ in the latter case is a direct consequence of RSA's homomorphic property and the ability to recover $x$ in the former case.

Suppose you are given the equations (with $c_i,a_i,b_i$ known):

$$c_i=(a_i\cdot x+b_i)^e\bmod N$$
$$\iff c_i=(a_i\cdot x+a_i\cdot b_i\cdot a_i^{-1})^e\bmod N$$
$$\iff c_i=a^e_i(x+b_i\cdot a_i^{-1})^e\bmod N$$
$$\iff c_i\cdot a^{-e}_i =(x+b_i\cdot a_i^{-1})^e\bmod N$$
$$\iff c_i' =(x+b'_i)^e\bmod N$$

With $b_i':=b_i\cdot a_i^{-1}$ and $c_i':=c_i\cdot a^{-e}_i$ which both only depend on known quantities, as you can always find multiplicative inverse $\bmod N$ (or if you can't in one instance, you can factor $N$) and you know $e,c_i,a_i,b_i$.

So you can use the ability to recover $y$ from $g_i=(y+f_i)^e\bmod N$ to recover (using the above equations) $x$ from $c_i=(a_i\cdot x+b_i)^e\bmod N$.


Encrypting data at rest using AES-GCM, where should I store MAC (Message Authentication Code)

My question is where (along with encrypted data? somewhere else?) [...] should I store the MAC in database?

In theory you can store the MAC wherever you want, as long as you store it and get the association right between MAC and ciphertext.
Practically however it's smartest to append the tag to the cipher text. This minimizes the chances that you screw up the association somewhere and it will make your implementation compatible with most libraries, which more often than not just append the tag and don't provide you explicitely with it.

  [H]ow (encrypted? hashed?) should I store the MAC in database?

Usually the MAC is stored in plain and this is actually covered by the usual security games and reductions. So an attacker can't even break the security of the scheme (ie decrypt messages in any attack model or forge a message) if the MAC-tag is available in plain. Thus there's no need for further encryption or hashing.


How to calculate RSA CRT parameters from public key and private exponent

The first (and hardest) step is to factor $n$; the easiest way to do this (given $e$ and $d$) is with this randomized procedure:

Select a random value $z$ from the range $(2, n-2)$
Compute the value $\lambda = (ed-1)/2^k$, where $k$ is that integer that makes $\lambda$ an odd integer.
Compute $t = z^\lambda \bmod n$.  If $t = 1$ or $t = n-1$, we fail on this selection of $z$.
Do this repeatedly, at most $k$ times:

Compute $u = t^2 \bmod n$.
If $u = -1$, we fail on this selection of $z$.
If $u = 1$, we have success (and we have the factorization $p = gcd(n,t-1)$, $q = gcd(n, t+1)$)
Otherwise, set $t = u$, and continue with the next loop

If we run through the above loop $k$ times without hitting either success or failure, then either we happened to have selected a $z$ that's not relatively prime to $n$, or $d, e$ are not a valid RSA exponent pair.

A random value of $z$ will fail at most half the time; so we run this procedure (selecting different random $z$ values) until it succeeds, and gives us the factorization.

Once we have the factorization of $n$, computing the rest of the CRT parameters is straight-forward.


Is it possible to generate a secure permutation F over 32-bit integers even if F(0) ... F(n) is public knowledge?

Yes, it is possible to implement the primitive asked, with a 32-bit block cipher that is secure (indistinguishable from a random permutation) no matter how many input-output pairs are known, keyed with a fixed secret randomly-chosen key. That's a standard building block in Format Preserving Encryption.

One such block cipher is: Louis Granboulan and Thomas Pornin, Perfect block ciphers with small blocks (in proceedings of FSE 2007).

Emil Stefanov and Elaine Shi's FastPRP: Fast Pseudo-Random Permutations for Small Domains (Cryptology ePrint Report 2012/254) claim a speed improvement, and review some earlier work.

Update: Ricky Demer kindly pointed another recent paper: Ben Morris and Phillip Rogaway, Sometimes-Recurse Shuffle, Almost-Random Permutations in Logarithmic Expected Time (Cryptology ePrint Report 2013/560).


Decrypting an Affine Cipher with known characters

You have 3 equations and 2 unknowns, so it is solvable, assuming a solution exists. You can plug this into any linear equation solver.

If you subtract equation 3 from equation 2, you get $a=-3$, and can solve for $b=75$. This fits equation 2 and 3, but not equation 1. So, no solution exists.


How to deduce enigma settings given a partial plaintext?

According to "Applied Cryptanalysis", the theoretical keyspace of Enigma is approximately $2^{366}$, but due to practical limitations, Enigma as used by the Germans only had a keyspace of approximately $2^{77}$. Given the power of some of the clouds out there (with GPUs and all), I bet you could do a brute-force attack of the 77-bit key space in a reasonable amount of time. Deep Crack could brute-force the 56-bit key space of DES in about 4.5 days. I'd think we could do much better than that today.

If you had a machine 100 times faster than Deep Crack, it would take about 265 years to do the brute force. If you had a thousand of these machines (not unrealistic given cloud computing), you could brute force it in 96 days (10000 machines would make it 9.6 days).

Since you are given a partial plaintext, however, I would think you could even do much better. Cryptanalysts during the war were able to do much better than brute force because of a protocol failure. The people enciphering messages would encrypt a session key with the daily key. They repeated the session key due to transmission errors. This allowed cryptanalysts to do statistical analysis once they had multiple messages captured from the same day. Without additional information from the OP though, it is unclear whether similar protocol weaknesses could be exploited.


FSB Hash Functions and Convetional hash Functions

That Wikipedia article is full of errors and false claims. Most importantly, FSB has not been proven to be as hard as an NP-complete problem. This is because the syndrome decoding problem is NP-hard in the worst case, but FSB uses random instances of the problem. Indeed, these random instances may be much easier to break than arbitrary instances. There is no guarantee that these random instances are actually hard, nor do we know how to generate NP-hard instances of decoding problems.

More generally, there is no known cryptographic primitive (of any kind) whose security is provably based on NP-hardness alone.


For Bob to prove that he signed the document, he needs to know something that other people do not.  In Alice's case, she knows her private key (we generally use the word private rather than secret when talking about signing keys), and we assume no one else knows it.

In Bob's case, everyone knows Alice's public key; hence if he used it somehow to sign a document, well, so could anyone else, and so that signature wouldn't prove that it came specifically from Bob.

There are other ways that Bob could try to prove authenticity (perhaps Bob and Alice share a symmetric key that no one else does; perhaps Bob has a secure connection with a Trusted Third party which is willing to vouch for Bob), however staying within the bounds of a simple asymmetric protocol, yes, Bob would need his own private key.


How are the four 8-bit permutation tables of Present cipher calculated?

In short: Trace back where bits come from in every byte in the output state (8 bytes) of the SP_network.

In one round, after we have xored the round key bits,
we have 8 bytes (a 64 bit word, with rightmost byte 0, leftmost byte 7 etc.
which in the linked software (which is byte oriented) is represented as state[0] to state[7]) are put nibblewise through the S-box: this is easy to do as a byte substitution as well. Then we trace where the bits in the post-permutation state come from (generated by a simple program, here the part for output byte 0, i.e. state[7]:)

bit 0 = byte 0, subbit 0  from byte 0, subbit 0
bit 1 = byte 0, subbit 1  from byte 0, subbit 4
bit 2 = byte 0, subbit 2  from byte 1, subbit 0
bit 3 = byte 0, subbit 3  from byte 1, subbit 4
bit 4 = byte 0, subbit 4  from byte 2, subbit 0
bit 5 = byte 0, subbit 5  from byte 2, subbit 4
bit 6 = byte 0, subbit 6  from byte 3, subbit 0
bit 7 = byte 0, subbit 7  from byte 3, subbit 4

We see that we use the bits 0 of the two S-box nibbles (which are 0 and 5 in the byte) to build a half-nibble (bits 0,1 or bits 2,3 etc.) of an output byte.  So we can start building four byte-indexed tables, say T0,T1,T2,T3 with the constraints that

T0[b] & 0x03 equals the bits 4,0 from SS[b] (i.e. the double nibble byte S-box.)
T1[b] & 0xc0 equals the bits 4,0 from SS[b]
T2[b] & 0x30 equals the bits 4,0 from SS[b]
T3[b] & 0xc0 equals the bits 4,0 from SS[b]

That way we can build up post-permutation byte 0 or state[7] as a bitwise-or
of masked outputs from these 4 tables (which we want to construct).

To build up the next to last byte 1 (state[6]) we have the following similar pattern:

bit 8 = byte 1, subbit 0  from byte 4, subbit 0
bit 9 = byte 1, subbit 1  from byte 4, subbit 4
bit 10 = byte 1, subbit 2  from byte 5, subbit 0
bit 11 = byte 1, subbit 3  from byte 5, subbit 4
bit 12 = byte 1, subbit 4  from byte 6, subbit 0
bit 13 = byte 1, subbit 5  from byte 6, subbit 4
bit 14 = byte 1, subbit 6  from byte 7, subbit 0
bit 15 = byte 1, subbit 7  from byte 7, subbit 4

So the same tables can be re-used but on different S-box output bytes.

Next we consider byte 2, state[5], again from the same output:

bit 16 = byte 2, subbit 0  from byte 0, subbit 1
bit 17 = byte 2, subbit 1  from byte 0, subbit 5
bit 18 = byte 2, subbit 2  from byte 1, subbit 1
bit 19 = byte 2, subbit 3  from byte 1, subbit 5
bit 20 = byte 2, subbit 4  from byte 2, subbit 1
bit 21 = byte 2, subbit 5  from byte 2, subbit 5
bit 22 = byte 2, subbit 6  from byte 3, subbit 1
bit 23 = byte 2, subbit 7  from byte 3, subbit 5

So to build up that byte we need the half-nibble built from the bits 1 of the S-box output (1,5 of the SS-box byte), so the constraints change slightly, where the order of the tables has been changed to get non-contradicting restraints (the lowest bits of T0[b] have already been fixed, etc.), so I use them cyclically:

T1[b] & 0x03 equals the bits 5,1 from SS[b]
T2[b] & 0x0c equals the bits 5,1 from SS[b]
T3[b] & 0x30 equals the bits 5,1 from SS[b]
T0[b] & 0xc0 equals the bits 5,1 from SS[b]

The same tables and masks can be re-used for byte 3 (state[4]) as witnessed by

bit 24 = byte 3, subbit 0  from byte 4, subbit 1
bit 25 = byte 3, subbit 1  from byte 4, subbit 5
bit 26 = byte 3, subbit 2  from byte 5, subbit 1
bit 27 = byte 3, subbit 3  from byte 5, subbit 5
bit 28 = byte 3, subbit 4  from byte 6, subbit 1
bit 29 = byte 3, subbit 5  from byte 6, subbit 5
bit 30 = byte 3, subbit 6  from byte 7, subbit 1
bit 31 = byte 3, subbit 7  from byte 7, subbit 5

Thirdly, for byte 4 (and again, similarly 5) we see

bit 32 = byte 4, subbit 0  from byte 0, subbit 2
bit 33 = byte 4, subbit 1  from byte 0, subbit 6
bit 34 = byte 4, subbit 2  from byte 1, subbit 2
bit 35 = byte 4, subbit 3  from byte 1, subbit 6
bit 36 = byte 4, subbit 4  from byte 2, subbit 2
bit 37 = byte 4, subbit 5  from byte 2, subbit 6
bit 38 = byte 4, subbit 6  from byte 3, subbit 2
bit 39 = byte 4, subbit 7  from byte 3, subbit 6

where we build succesive half-nibbles all from the different
masks of the combination of bits 6,2 (bit 2 from a single S-box)
of the SS-box output. So again we can build new constraints, going on cyclically from before:

T2[b] & 0x03 equals the bits 6,2 from SS[b]
T3[b] & 0x0c equals the bits 6,2 from SS[b]
T0[b] & 0x30 equals the bits 6,2 from SS[b]
T1[b] & 0xc0 equals the bits 6,2 from SS[b]

where we can re-use the exact same bitwise-or recipe for byte 5.

Finally, for bytes 6 (and 7) we get as the origins:

bit 48 = byte 6, subbit 0  from byte 0, subbit 3
bit 49 = byte 6, subbit 1  from byte 0, subbit 7
bit 50 = byte 6, subbit 2  from byte 1, subbit 3
bit 51 = byte 6, subbit 3  from byte 1, subbit 7
bit 52 = byte 6, subbit 4  from byte 2, subbit 3
bit 53 = byte 6, subbit 5  from byte 2, subbit 7
bit 54 = byte 6, subbit 6  from byte 3, subbit 3
bit 55 = byte 6, subbit 7  from byte 3, subbit 7

So we use the combination of bits 7,3 (or bit 4 from a single S-box)
from different bytes to form this byte. So the next set of new constraints
becomes:

T4[b] & 0x03 equals the bits 7,3 from SS[b]
T0[b] & 0x0c equals the bits 7,3 from SS[b]
T1[b] & 0x30 equals the bits 7,3 from SS[b]
T2[b] & 0xc0 equals the bits 7,3 from SS[b]

Now we can gather the results: to actually find T0[b] we
consider all we know about it from before:

T0[b] & 0x0c equals the bits 7,3 from SS[b]
T0[b] & 0x30 equals the bits 6,2 from SS[b]
T0[b] & 0xc0 equals the bits 5,1 from SS[b]
T0[b] & 0x03 equals the bits 4,0 from SS[b]

and compute the table directly. It will be the table pmt_3 from
your linked software. This code (gist on GitHub) will compute these combined tables (in a slightly different order I believe then used in the linked software) to see how to do this in more detail.


Are there maximal rsa modulus keysize above which security start decreasing?

With current known attacks increasing key size will improve security. Providing you follow current best practices for selecting p and q, not to close together neither to small. Etc.
It is possible but unlikely there will be some future attack on RSA or integer factorization which gets easier beyond a certain size. We already have different best algorithms for integer factorization depending on size but bigger is still better.
https://en.wikipedia.org/wiki/General_number_field_sieve is currently best for very large numbers (with no special form). But for numbers less than 100 digits or so https://en.wikipedia.org/wiki/Quadratic_sieve is faster.

Obviously standardized well known implementations are more secure than anything homegrown and this will likely trump key size.

Currently RSA is best attacked by integer factorization and this will likely remain in the near future, though there are no proofs RSA is as hard as Integer factorization.


Why RSA must make sure that $\gcd(e,\varphi(n)) = 1$ instead of $\gcd(e,n) = 1$?

You want to be able to encrypt a message and decrypt it, that is translated to:

$m^{ed} \equiv m^1 \equiv m \pmod n$

But why does this work? Since $ed \equiv 1 \pmod{\varphi(n)}$

If $\gcd(e,d) \neq 1$ then $e$ and $d$ are not coprime then $ed \not \equiv 1 \pmod{\varphi(n)}$. So $e$ must be coprime with $\varphi(n)$ to have a modular multiplicative inverse.

Also $\gcd(e,n)=1$, since the public key is presented as $(e,n)$. Then you trivially can compute a factor of $n$ if $e$ is not coprime.


Shamir's Threshold Scheme (Theory Part, Need some help understanding a term that I can't find online)

By definition, $\max(a,b)$ is the largest of $a$ and $b$. That's also the meaning in many computer languages, e.g. Python's max.

Thus $p>\max(S,n)$ means: $p>S$ and $p>n$.


Is the padding wrong on the "Length Extension Attack" Wikipedia page example?

50- byte padding staring with 1 and rest is zero ( each \ is a byte)
\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00

8-byte size part of padding where the size is encoded ( SHA-1 has 64-bit length encoding in the padding that makes 8-byte)
\x00\x00\x00\x00\x00\x00\x02\x28

0x228 = 552 and we have 69 bytes of message size.
That is correct. 55-byte message and 14-byte secret make a 69-byte message.
The message in bits makes 552 bits that are over one block of SHA-1 that has a 512-bit block size. So in total, we need 1024 bits for hashing, two blocks. 64 bits reserved for the message size. This left 960 bits. Now subtract the 552-bit message size and we have 408 bits. So we need 51 bytes of padding starting with 0x80 but we have 50, i.e. $\color{red}{\text{1-byte is missing. Your calculations are correct}}$.

We should have;
$$\underbrace{secret}_{14-byte}\mathbin\|\underbrace{message}_{55-byte}\mathbin\|\underbrace{100\ldots00}_{51-byte \text{ padding 10 part}}\mathbin\|\underbrace{000\ldots 0228}_{8-byte \text{ length part}}$$

SHA-1 padding rule

append the bit $\texttt{1}$ to the message e.g. by adding byte $\texttt{0x80}$ if message length is a multiple of 8 bits i.e. byte-oriented.

append $0 \leq k < 512$ bits of zeroes, such that the resulting message length in bits is congruent to $$−64 \equiv 448 \pmod{512}$$

append the original message length, as a 64-bit big-endian integer.
Thus, the total length is a multiple of 512 bits.

The real extension;
Wikipedia doesn't show the required padding after &waffle=liege is appended. This is 13 bytes text and the size of the message will be $1024+13*8= 1128$. Therefore we will need 3 blocks for the extension that makes total of 1536 bits. 64 bits of this will be the new size encoding and this will need 344 bits of $1000.000$
$$\underbrace{secret}_{14-byte}\mathbin\|\underbrace{message}_{55-byte}\mathbin\|\underbrace{100\ldots00}_{51-byte \text{ padding 10 part}}\mathbin\|\underbrace{000\ldots 0228}_{8-byte \text{ length part}} \mathbin\|\underbrace{\text{&waffle=liege}}_{13-byte \text{ extended message}} \mathbin\|\underbrace{100\ldots00}_{43-byte \text{ padding 10 part}} \mathbin\|\underbrace{000\ldots 0468}_{8-byte \text{ extended length part}} $$
In other view;
$$\text{SHA-1}(\text{secret_key}\mathbin\|\text{message}\mathbin\| \text{pad1}\mathbin\|
 \text{appended_data} \mathbin\| \text{pad2})$$


Why is GCM only usable for ciphers with a 128-bit block size?

The field polynomial used for GHASH limits most definitions to 128-bit block size. That does not mean you could not define it for other sizes – the proposal defined it for 64-bit as well (pdf, see Appendix A) even if NIST did not standardize that.

However, defining it for arbitrary block sizes would be more difficult. You would need to define a deterministic method for constructing the polynomial and the changes that entails (see the document above). Since 64-bit block ciphers are usually considered too small these days anyway and no larger block sizes are in common use, there is no need to do that.


Floating-point arithmetic is just rounded arithmetic on a simple integer-based representation of a subset of real numbers.  Floating-point arithmetic is not unpredictable—on the contrary, it is extremely well-standardized in IEEE 754 (paywall-free), unlike, e.g., signed integer arithmetic which sometimes traps or wraps or behaves unpredictably in cases of overflow, shift of negatives, etc., depending on hardware, programming language, compiler, and operating system.
Every computer you are likely to encounter supports IEEE 754 arithmetic, and most of them will by default behave in exactly the same way (32-bit x86 with x87 FPU excepted, though configuring it to do IEEE 754 binary64 arithmetic is easy), giving bit-for-bit identical answers, for the most common arithmetic operations: addition, subtraction, multiplication, division, and a few others.  Floating-point arithmetic is typically very fast, is vectorized by many CPUs, and even usually turns out to be constant-time on finite normal numbers.
Specifically, a binary64 (or double-precision) floating-point finite normal number is a real number of the form $$2^e\cdot(1 + f/2^{52})$$ where $f$ is an integer in $\{0,1,2,\dots,2^{52} - 1\}$ and $e$ is an integer with $-1021 \leq e \leq 1023$.  There are a few other binary64 floating-point numbers, $\pm\infty$ and subnormals, and there are also floating-point values that are not numbers, namely NaN values, but they're not likely to matter for cryptographic applications.
The basic arithmetic operations are defined so that for any floating-point numbers $x$ and $y$, $x \oplus y = \operatorname{round}(x + y)$, where $\oplus$ is floating-point addition and $\operatorname{round}$ yields the floating-point number nearest to the real number $x + y$, or the floating-point number with least-significant significand digit zero in the case of a tie.  (Yes, you can configure other rounding modes, but by default this is the one you will get.)
There are subsets of floating-point numbers on which $x \oplus y = \operatorname{round}(x + y) = x + y$.  For example, the set of integers in $[-2^{52}, 2^{52}]$ have this property.  The hash127 paper you cited uses this property to reliably compute integer arithmetic modulo the large prime $2^{127} - 1$ using floating-point arithmetic on an eight-digit representation $t_7 2^{112} + t_6 2^{96} + \cdots + t_1 2^{16} + t_0$, where each term $t_i 2^{16i}$ is represented by a floating-point number.
Floating-point rounding is reliable enough that you can use it to mask off the top or bottom bits of an integer, e.g. to get the limbs $t_i$ in the above form.  For example, let $x = \text{0x896da38f}$, or 2305663887 in decimal.  Suppose you want to compute $y = x \mathbin\& \text{0xffff0000} = \text{0x896d0000}$, i.e. mask off the bottom sixteen bits of $x$, using binary64 arithmetic, which has 53 bits of precision.  You can add a sufficiently large number that the bottom sixteen bits get rounded away, and then subtract it: $(x \oplus 3 \cdot 2^{16 + 53 - 2}) \ominus 3 \cdot 2^{16 + 53 - 2}$ gives $2305622016$ in decimal, or $\text{0x896d0000} = y$ as intended.  Here $3 \cdot 2^{16 + 53 - 2}$ is a binary64 floating-point number already, so it can be represented exactly, and $\oplus$ and $\ominus$ are floating-point addition and subtraction in the default rounding mode.
However, while floating-point arithmetic can be reliably exploited for fast constant-time vectorized integer arithmetic, what floating-point arithmetic does not provide is bitwise operations or Galois field arithmetic.  For example, there's no easy fast way with floating-point arithmetic to compute $f + g$ for degree<=32 polynomials $f, g \in (\mathbb{Z}/2\mathbb{Z})[x]$ or two elements $f, g \in \operatorname{GF}(2^{32})$—also known as 32-bit xor.
So while you can do integer arithmetic and mask off chunks of an integer at a time with floating-point arithmetic, manipulating individual bits is tricky, and manipulating them in parallel as vectors is even costlier, whereas integer units in CPUs do it nearly effortlessly.  Thus it would be hard to compute, say, the Keccak or Salsa20 permutations fast with floating-point arithmetic—Keccak probably even harder than Salsa20, because at least Salsa20 has some 32-bit integer addition that could take advantage of a floating-point adder.
Could you use floating-point arithmetic to build a CSPRNG?  Sure—you could even implement Keccak or Salsa20 using floating-point arithmetic, and you might even conceivably want to do that in some contexts such as Python in which integer arithmetic is notoriously leaky due partly to the small integer cache (if for some reason you couldn't just write a C extension).
Would it beat speed records for existing CSPRNGs at a comparable standard security level?  Probably not, and any cryptanalysis of it would no doubt be based on the bit-string-to-bit-string functions just like any integer- or bit-based CSPRNG rather than any numerical analysis.
(I'd guess the floating-point representation would probably just make the analysis more irritating, so it would get less scrutiny.)
Note that the ‘hash’ of hash127 does not mean fixed preimage-resistant hash function like MD5 or SHA3-256.  Rather, like Poly1305, hash127 is a universal hash family (paywall-free; Wikipedia)—specifically, hash127 a family of functions $H_r$ indexed by $r \in \mathbb{Z}/(2^{127} - 1)\mathbb{Z}$ with difference probability $\Pr[H_r(m_0) - H_r(m_1) = \delta]$ over uniform random $r$ bounded by $\ell/2^{128}$ for every difference $\delta$ and all messages $m_0$ and $m_1$ up to $\ell$ bytes long.


Well, first of all, this is not a generic 'public-key' question.  With RSA, it can make sense to talk about 'encrypting with the private key', for most other public key algorithms, there's isn't an obvious interpretation.  For example, with DSA, the public key operation (which is a signature verification) is 'plug the data from the signature, the hash of the data and the public key into a formula; the signature passes of both sides are the same value'.  There's no obvious way to use this type of operation to encrypt something.

Now, in your question, you ask whether encrypting with the RSA private key is secure.  Well, that depends on what you mean by secure; what precisely are you attempting preventing someone from doing?  In one sense, it is not secure at all; anyone who has the public key can decrypt the message.  Since it is generally true that anyone can get the public key, well, this means that this is not at all a secure encryption method.

On the other hand, you might not be assuming that this is a secure encryption method; this might be an attempt to simulate RSA signature generation.  Here, you have to be careful; RSA using padding methods to translate between the message being encrypted/signed into a value to give to the raw RSA function.  The security properties for an encryption padding method are different from the security properties for a signature padding method; in fact, there are real world secure encryption padding methods (for example, RSAES-PKCS1-v1_5 with e=3) that could be insecure if used as a signature padding method.

However, you may simply be asking "would the key be secure"?  In some sense, that is irrelevant; usually, the only reason an attacker wants the keys is that would allow him to perform some operation; if he can perform those operations without the keys (because, for example, of the vulnerabilities mentioned in the above two paragraphs), then he doesn't need the keys.  However, if you are still concerned about the keying data, well, it turns out that RSA is safe; performing RSA operations (even on attacker chosen values) doesn't leak the private key.


Normally you don't want to reverse the encryption used within a DRBG. Schemes like PKCS#7 padding and CTS are required to deterministically reverse the padding during decryption. If you just want to have a final block, you should be fine by using zero padding until the end of the block.

Of course, if this zero padding is actually harming the output of your DRBG depends on the algorithm.


Can CMAC be used as a 128bit Key Derivation Function?

CMAC(masterKey, i) should generally suffice, yes. Note that you would need to specify an encoding for i (e.g. octet string consisting of the big endian encoding of i, left-padded with zero valued octets up to 4 octets).

It's probably better to implement one of the schemes defined in NIST SP 800-108: "Recommendation for Key Derivation Using Pseudorandom Functions" though. Note that CMAC is a Pseudorandom Function (PRF) and is mentioned explicitly in this standard.

I'd recommend the NIST SP 800-108 counter mode (section 5.1), which is relatively commonplace and easy to implement. Note that the counter i in the standard is different from your definition of i. The i in the standard is used to derive more keying material for a single key than can be generated by the PRF (i.e. more than 128 bits in the case of AES-CMAC). Your i should be encoded in the Context variable if you follow the standard to the letter.


An s-box is a bijective function $f: \{0,1\}^b\rightarrow\{0,1\}^b$. This reduces the question to "how many of those $f$ exist".

To see this easily, imagine domain and image of this function as two boxes with $2^b$ elements. How many different sets of arrows can you imagine between those two sets?

For the first arrow, you have $2^b$ choices. For the second arrow, you have $2^b -1$ choices. For the third, $2^b-2$, and so forth to the last arrow, where there's one choice left.

Multiplying those together, you would get $2^b(2^b-1)(2^b-2)\dots 1=2^b!$ possible s-boxes, so in your 16-bit case that makes $2^{16}!$ possibilities.

To put this more mathematically, an s-box is a permutation of $2^b$ elements, and there are $2^b!$ such permutations.


linear computations over bilinear pairings

For clarity, I will use an additive notation in the groups $\mathbb{G}_1$ and $\mathbb{G}_2$, and denote group elements with the "$x$" letter, not "$e$".

For all $x_1, x_3 \in \mathbb{G}_1$ and $x_2, x_4 \in \mathbb{G}_2$, we have the following:

\begin{eqnarray*}
e(x_1 + x_3, x_2 + x_4) &=& e(x_1, x_2 + x_4) e(x_3, x_2 + x_4) \\
&=& e(x_1, x_2) e(x_1, x_4) e(x_3, x_2) e(x_3, x_4)
\end{eqnarray*}

(First equation is by linearity of the pairing for its first operand, second equation is by linearity for its second operand.)

Therefore, one can have the property you seek only when $e(x_1,x_4)$ and $e(x_3,x_2)$ happen to be opposite of each other, which is not true in general (unless the pairing is degenerate, in which case it is quite uninteresting).


Encoding numbers that can be decoded mentally?

I wouldn't try and do this mentally. Whatever you come up with will be insecure, slow and error prone.

Here's what I would do:

Each box would have a QR-code on it that you print and attach to the item.
You then scan the item with your phone.
Your phone has 128-bit key saved to it that is unique to that device.
The phone decrypts the QR code and displays the associated data inside the QR code.

The bigger QR-codes can store enough data that you can actually do the crypto properly with the proper IVs and authentication tags. AES in GCM mode would be my suggestion.

This solution has the advantage that it's very quick to decode the message on the boxes, the underlying scheme is secure, and QR-codes have automatic error correction capabilities, so they can resist damage.

This has to be better than trying to do it in your head.


Is the following non-interactive zero-knowledge set membership protocol provable secure?

Reading the last sentence:

Can an adversary find a $c’$ such that $c’ - c= 0$ in a field. This follows from the definition of a field, whenever $c’ != c$


Yes, that should be secure. It seems however that your problem lies with the secure random number generator and that you are using a KDF to overcome those. Basically you are using a KDF as key generator; no keys are derived from another / master key.

It seems more obvious to use a DRBG / CPRNG (deterministic random bit generator / cryptographically secure pseudo random number generator - there are probably more names) and seed it with random values from the system and the user. After that you can just extract the key bytes, and you would still be left with a (fast) RNG that you can reuse / reseed - something you will likely need later on.

Many API's already provide these out of the box, and usually they are pre-seeded as well, so you may just have to add your user generated entropy to the state by mixing in additional seed data. Nothing stops you from adding HKDF + OtherInfo in addition to the DRBG of course, but that is not required.


Why does choosing the first coprime e greater than half of φ(n) result in the same d (private exponent)

When choosing the public exponent $e$, if the value chosen is the first coprime after $\phi(n)/2$ then the resulting public and private exponents are equal.

Well, yeah, that'll always be true.

  Why does this happen?

We have $e=d$ whenever we have both of the following true:

$$e^2 \equiv 1 \pmod{p-1}$$

$$e^2 \equiv 1 \pmod{q-1}$$

Now, if $e = (p-1)(q-1)/2 + 1$ (which is always the first coprime after $\phi(n)/2$), then if we denote $k = (q-1)/2$ (which is an integer),

$e^2 = ((p-1)(q-1)/2 + 1)^2 = ((p-1) k + 1)^2 \equiv 1^2 = 1 \pmod{p-1}$

By symmetry, we also have $e^2 = 1 \pmod{q-1}$ as well, and so $e=d$ works in this case.

Furthermore, whenever we have both the following hold:

$$e \equiv 1 \pmod{p-1}$$
$$e \equiv 1 \pmod{q-1}$$

then we'll have $M^e \equiv M \pmod{N}$ (for all $M$), that is, the RSA operation will always give us the original plaintext.  These are also both true in the case of $e = \phi(N)/2 + 1$, and so such an $e$ will also always have plaintext=ciphertext, which is what you observed.

  Is this even a problem?

If you intend to use $\phi(n)/2 + 1$ as your public exponent, yeah, that's a problem.  Exposing such a value also makes $n$ easy to factor; however the attacker doesn't need to factor to break the system in this case.

However, if you use a more normal public exponent, say, 3 or 65537, it's pretty irrelevant.

  Selecting only public exponents that are primes might eliminate the possibility of this occurring, but I have neither tested nor seen that it's a requirement in the RSA algorithm.

Well, what's most common for RSA implementations is to pick $e$ first (and it makes sense to pick it as a small value), and then select primes $p$ and $q$ such that $p-1$ and $q-1$ are relatively prime to $e$.  If you do that, then $e=d$ cannot happen, because if $1 < e < \sqrt{p-1}$, then we trivially have $e^2 \not\equiv 1 \pmod{p-1}$.

However, even if you pick $e$ large (for whatever reason), as long as you do it randomly, then the probability that both $e^2 \equiv 1 \pmod{p-1}$ and $e^2 \equiv 1 \pmod{q-1}$ both hold is negligible.


$d$ must indeed be an integer.

To calculate $d$ you need to calculate $d=e^{-1}\bmod{\phi(n)}$ which is called the modular multiplicative inverse of $e\bmod{\phi(n)}$. For $d$ be computable you need to ensure that $$\gcd(e,\phi(n))=\gcd(e,(p-1)(q-1))=1$$

holds, which isn't the case with your sample parameters as $\gcd(3,60)=3\neq1$.

As fgrieu pointed out in the comments you can find the private exponent by finding the smallest $k$ for which $(k\cdot\phi(n)+1)/e$ is an integer. The run-time of this approach likely will grow linearly with the size of the $e$ value which is in the order of $2^{16}$ usually.

Of course $k$ isn't unique unless you take the smallest possible $k$, meaning there will be other (larger) values of $k$ yielding a valid decryption exponent.


Reverse output of general Fibonacci LFSR

The Fibonnacci LFSR whose feedback polynomial is the reverse of the given LFSR polynomial will produce the sequence in reverse. Here by
reverse is meant $x^mg(x^{-1})$ where $g(x)$ (of degree $m$)
is the feedback polynomial
of the given Fibonnacci LFSR.  Note that the initial loading
of the LFSR must be changed to the ending of the given output sequence
(in reverse order).


Given PRNG $G(s)$, why is $G(s) || G(s+1)$ not a PRNG?

$L$ is not necessarily a pseudorandom generator, but it may be. Hence, there is no hope of proving that $L$ is not a pseudorandom generator from what you are given. Rather, you must exhibit a pseudorandom generator $G$ such that $L$ is not a pseudorandom generator. Here is the canonical example with expansion factor $n+1$.

Let $f$ be a one-way permutation (i.e., an injective, length-preserving one-way function). Then it is known that the following is a pseudorandom generator with expansion factor $n+1$:

  Choose uniformly a seed $s$ of even length $s_1s_2\dots s_{2n}$.
  Compute $b = \sum_{i=1}^n s_is_{n+i}$ (with arithmetic in $\mathbf{F}_2$).
  Output $f(s_1s_2\dots s_n)s_{n+1}s_{n+2}\dots s_{2n}b$.

Now, if $s$ is uniformly chosen, with probability $1/2$ its last bit will be $0$, meaning that $s+1$ will be just $s$ with the last bit ($s_{2n}$) flipped, and in turn it means that $G(s+1)$ will equal $G(s)$ except possibly in the last two bits. Hence, a distinguisher can check whether the second half of its input string equals the first one disregarding the last two bits of each. If the string is $G(s)G(s+1)$, this happens with probability at least $1/2$, whereas if the string is truly random this happens with probability $1/2^{n-2}$.


The NIST site http://csrc.nist.gov/publications/PubsFIPSArch.html lists FIPS 113 as Withdrawn: Sep 2008. The Federal Register https://www.federalregister.gov/articles/2005/07/15/05-13992/proposed-withdrawal-of-ten-10-federal-information-processing-standards-fips gives a reason:

  FIPS 113, Computer Data Authentication, specifies an algorithm for
  generating and verifying a Message Authentication Code (MAC). Since
  the algorithm is based on the Data Encryption Standard, which has been
  recommended for withdrawal, NIST plans to recommend the use of newer
  techniques for data authentication based on more secure algorithms.


What are some of the alternatives to password based file encryption?

Hardware tokens (such as smart cards, FIDO U2F keys, and other secure storage elements), and normal files can all directly store cryptographic keys. For example, it's recommended to configure SSH servers to only use cryptographic key files.