Optimising Pollard's Rho algorithm for large semi-primes I have programmed an implementation of Pollard's Rho factoring algorithm using C++ and the GMP library.

It is reasonably fast with large numbers, however I haven't implemented any form of cycle detection (I just try and avoid the problem, see below), and it struggles with small numbers.

Here is the pseudo code of my implementation:

input n
x = 2
y = 2
d = 1
c = 1
z = 1
failed = 0
temp = 0

while d == 1 or d == n
    z = 1
    failed = failed + 1
    if failed = sqrt(n)
        c = c + 1
        failed = 0

    repeat 100 times:
        x = x^2 + c mod n
                repeat twice:
                    y = y^2 + c mod n
        temp = abs(x - y)
        z = z * temp

    d = gcd(z, n)

I was wondering how I could improve the efficiency of this algorithm? If I'm using large semiprimes, do I need to worry about cycle detection?

Might as well make this an answer, enough comments. This'll answer your latest questions:

I don't think they have to start at 2, however they need to start at the same value (as per the cycle detection algorithm). So 2 is the simplest choice, and since the function is assumed to trace a pseudorandom sequence, it doesn't really matter where you start.
The function can be any pseudorandom function satisfying the Rho property (gcd is conserved by iterating through it, basically it inherently "remembers" whenever you capture a factor of $n$ without having to store all the numbers, this is the core concept). But $x^2 + c$ is the simplest one, so it's often the best choice as it's fast to calculate and produces a relatively chaotic sequence mod $p$.
$c$ can be negative, because the function is taken modulo $n$, so a negative value is still positive, however it cannot be $0$ or $−2$ (to prevent trivial cycles in $x = 0$ and $x = \pm 1$).
Yes, I said "on the order", this is a probabilistic algorithm so it's usually either a bit less, either a bit more.. it depends on $c$ and on the factor found.  The idea being that it's very fast on small factors (~20 digit prime factor maximum, so I would say a 40-50 digit semiprime is the best you're going to get with Pollard's Rho in reasonable time, which is still pretty good considering its simplicity)


How to Formalize Noise Protocol Messages I try to understand the messages of the Noise Protocol Framework. The handshakes are based on Diffie-Hellmann key exchange.
This is an example for a handshake pattern:

-> e
<- e, ee, s, es

I try to formalize the handshake with mathematical descriptions.
For example the mathematical description of the first message is:
. Where  is a generator and  is the private ephemeral key of the sender.
But I don't understand how the values ee and es are calculated.
How can these patterns be descriebed mathematically?

ee and es aren't values, they're function invocations.

ee denotes the use of a Diffie-Hellman key exchange using two ephemeral keys, es denotes the use of a Diffie-Hellman key exchange using an ephemeral key and a static key. The first letter is the initiator, the second is the responder.

So it's just $ee = DH(e, re)$, $es=DH(e,rs)$, $se = DH(s, re)$, $ss = DH(s, rs)$, where $DH(i,r)$ is the Diffie-Hellman exchange function applied to the $i$nitiator's key and the $r$espoder's key.


How does DES decryption work? Is it the same as encryption or the reverse? If DES decryption is the same as encryption done in reverse order, then how can the reversed S-Box convert 4 bits into 6 bits?

DES is based on a Feistel construction - while the one-way function used is.. well.. one-way, you don't need to reverse it at all to "decrypt" (otherwise you are correct we would have a problem). Look at this diagram, specifically the decryption one:

As you can see, even though one half of the ciphertext is passed through the one-way function, there's always a copy of it remaining. In this case, $L_{n + 1}$ goes through the one-way function to mask $R_{n + 1}$, but still becomes one half of the ciphertext, which lets you use it again during decryption to undo the XOR operation you used to mask the other half of the ciphertext.

Then you keep doing that for each round (using the round keys in reverse) and you end up with the plaintext. No information is lost during the encryption process, the one-way function is simply used to mask each half in turn in an interleaved fashion (which can be done again during decryption in the opposite direction, but only if you have the key).

Ultimately decryption is very similar to encryption, a common feature of Feistel ciphers in general. In fact with some arrangements the only difference is the order of the subkeys, which is (or at least was) a big advantage as it makes implementation easier on limited devices, as you can mostly reuse the encryption code for decryption.


Distinguishing joint probability distributions Assume that we have a probability distribution $P(X,Y)$ for the joint probability of random variables $X$ and $Y$. Let $P(Y, Z)$ be analogous distribution for $Z$ and $Y$. Based on these we can define a joint probability distribution of $P(X,Y,Z)$.

Let, $P'(X,Y)$ and $P'(Y,Z)$ be analogously probability distributions where it is known that $P'(X,Y)$ is computationally indistinguishable from $P(X,Y)$ and $P(Y, Z)$ is computationally indistinguishable from $P'(Y,Z)$. Based on these we define a joint probability distribution $P'(X,Y,Z)$.

Do the indistinguishability conditions on the initial distributions imply that $P(X,Y,Z)$ is computationally indistinguishable from $P'(X,Y,Z)$?

Obviously not; one can easily define probability distributions $P$ and $P'$ such that $P(X,Y)=P'(X,Y)$ and $P(Y,Z)=P'(Y,Z)$, but $P(X,Y,Z) \ne P'(X,Y,Z)$

For one such example, take $P$ be the probability distinguish where $X$, $Y$ and $Z$ are uniformly and independently distributed boolean variables; and $P'$ be the probability distribution that $X$ and $Y$ are uniformly and independently distributed boolean variables, and $X=Z$ with probability 1.

Now, $P(X,Y)=P'(X,Y)$ (because, in both probability distributions, each possible combination of boolean variables will occur with probability 0.25), and similarly $P(Y,Z)=P'(Y,Z)$.

However, $P(X,Y,Z) \ne P'(X,Y,Z)$ in an computationally easy manner, because with a single sample of the probability distribution, we can check if $X = Z$ (can guess $P$ if it is false, and $P'$ if it is true); that gives us a distinguisher that succeeds with high probability.


Does the plaintext have to be at least as long as the key in Polyalphabetic substituion cipher In polyalphabetic substitution cipher, if we have a key $k$ (a string of letters) of length $n$ does the plaintext $m$ (also a string of letters) have to satisfy $|m| \geq n$?

Also, side question, do we have to include a requirement that at least one letter in the key is different from the others? Because otherwise it becomes a simple shift cipher (Not poly at all)

I'm not aware of any classical polyalphabetic ciphers where the key could not be longer than the message.

For the Vigenère cipher, the key is, effectively, repeated to make it as long as the message.  There is no reason why it could not be repeated less than once, effectively discarding the unnecessary characters at the end of the key.

Similarly, in the autokey cipher, the key is dynamically extended by appending either the plaintext or the ciphertext message to it, ensuring that the extended key never runs out of characters.  If the message is no longer than the key, however, this extension is never needed, and the autokey cipher behaves exactly like the Vigenère cipher.

In fact, if the key for the Vigenère or autokey cipher is:

at least as long as the message,
composed of purely random characters, and
never used to encrypt more than one message,

then the cipher becomes an unconditionally secure one-time pad.  This is the most secure kind of cipher, being provably impossible to decrypt without knowledge of the key.  Alas, the strict requirements on the key — not the least being that it needs to be at least as long as the message being encrypted — make it rather impractical for most purposes.

As for your side question, obviously, if you deliberately choose only keys that consist of a single repeated character, then a Vigenère cipher becomes just a simple shift cipher.  However, if you're using a one-time pad with random keys, there is a (very small) probability that all the random characters will be the same, and that's perfectly fine.

In fact, if you threw out such keys, your key selection process would no longer be perfectly random, and so an attacker could potentially learn some information about the plaintext just by inspecting the ciphertext and knowing that the key cannot be one that has all its characters identical.


What happens if a nonce is reused in ChaCha20-Poly1305? In ChaCha20-Poly1305, I know that reusing a nonce loses confidentiality and integrity for all messages encrypted with the (key, nonce) pair.

However, is security affected for those messages encrypted with the same key but different nonces?

If you reuse a nonce, you lose confidentiality for the messages with that nonce. Messages with other nonces retain their confidentiality.

However, the attacker can also attack the MAC part (Poly1305) and generate a third and more messages with the same nonce. See: Why is Poly1305 popular given its 'sudden death' properties?

So unless you have a way to rule out messages with that nonce in the future, for example due to the protocol enforcing a new nonce each time, you cannot trust messages encrypted with that key any more. If you can rule them out, messages with other nonces cannot be forged, because the MAC key is generated from the encryption key and the nonce.


Is AES in XTS mode insecure for data stream encryption? Can anybody explain to me why AES in XTS mode is supposedly insecure for data stream encryption? I have been unable to find a clear explanation for this.

From Ptaeck's site (here) (You linked this)

It’s complicated. It’s a wide-block tweakable mode built out of a narrow-block tweakable mode, it uses two keys unnecessarily, and it uses ciphertext stealing to handle variable-length inputs. Another way to say “complicated” is “hard to prove correct”.

This essentially means that it's easy to implement incorrectly, and might not be as secure as is thought in the first place.

It’s unclear what XTS’s goals are. It’s ECB-like. It can’t do a perfect job of providing privacy. It’s not authenticated. Attackers can rewrite plaintexts. It’s hard for a cryptographer to know what they’d be trying to prove. “behavesLikeXTS”? OK, and?

The lack of authentication is a big issue when not used for disk encryption: if an attacker can modify the ciphertext in transit that can't be detected by the recipient. The classic example of this would be rewriting a transaction's recipient or amount to get an attacker the money.

The wide-block-of-narrow-blocks property weakens XTS unnecessarily. As the disk rewrites a given sector, attackers can collect fine-grained (16 byte) ciphertexts. They get to manipulate ciphertexts surgically. It would have been possible to define a “native” wide-block tweakable cipher without that property, but that wouldn’t have been as performant.

The bit about ECB-like means that patterns in the plaintext data at certain scales are detectable in the ciphertext. That's bad, in some cases it can allow an attacker to determine the content of the plaintext.

This is also an issue due to the lack of authentication. The attacker can observe changes in the state of the ciphertext, and responses to their changes to the ciphertext. This makes attacks easier. Not necessarily practical, but not something you want to do if possible.

An ideal cipher should be computationally infeasible for an attacker to modify without detection (authenticated, integrity-preserving), should reveal nothing about the plaintext other than its size (confidential), and uniquely bound to a given origin (authentication). XTS provides no authentication, doesn't preserve integrity, and has some weaknesses in its confidentiality. It's the best we have for disk encryption without a specialized filesystem, but it's a terrible choice for anything without the constraints of full disk encryption on a general-purpose filesystem.


Encryption / Decryption method secure I was wondering whether this encryption / decryption flow is very solid / secure. I encrypt the data using AES CBC 256 bit with an static IV.

When the user logs in with his Firebase account (first phase of authentication), he gets the option to enter a security password. After that is done, some encryption values will be retrieved like the prefix, suffix and IV. I create the key as following: prefix + given key + suffix. After that I decrypt a retrieved string, and if I get a certain text back, I know it is the right key and start decrypting it for this session.

So to sum it up:

Log in with Firebase
Get encryption values like prefix, suffix, IV and encrypted string
Let user enter password
Create an key in the format prefix + given password + suffix and apply an static IV
Use the generated key to decrypt a string
If it is successfully decrypted, use the key for this session

Note: I won't use public / private key exchange due to reasons.

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.


Does hashing a hash of a password over and over again increase its security? I've heard of password cracking attacks using a list of commonly used passwords. Suppose in my situation, I can never be sure about the strength of the password, that a user inputs to my interface. So if I compute the SHA 256 hash of the user inputted password, then hash the hash again n times will that increase its overall probability of NOT being cracked ? If so what should be a reasonable value of n.  Thanks everyone in advance!!!

What your describing is the core of many password hashing algorithms like bcrypt or pbkdf2. However, these are all complicated functions which don't just iterate. They are very commonly used with salt. If you would hash a password as you described n times, a reasonable choice would be bigger then 100.000.

However this is only for storing the password. If you would do this for, say, a website, it would take about 2 seconds. And if you're clients arent finding it nice to wait that long, you should lower it.


E-voting: public tallying vs. vote selling There are many design goals for an e-voting system. My question concerns a conflict between 2 particular goals:

A voter should be able to verify that their vote was correctly tallied
A voter should not be able to prove how they voted (to prevent vote selling)

I've looked into various e-voting systems and none of them appear to be able to satisfy these 2 goals simultaneously.

  Some researchers argue that end-to-end auditability and receipt-freeness should be considered to be orthogonal properties. (Wikipedia)

Is this an unsolved problem?

The second property is formally called receipt freeness.  Any voting system based on probabilistic encryption cannot be receipt free, because the voter uses  a random value to construct the vote, this random value can serve as a receipt.
The solution given to this problem is by having an authority create the vote and the voter simply selects it from a presented list.
The first protocol to achieve this is as far as I know is the one described in the paper Receipt-free secret-ballot elections from Benaloh and Tuinstra. A more widely used example is  Efficient receipt-free voting based on homomorphic encryption from Hirt and Sako.
You can check these references especially the second one on details about how to achieve verifiability.


Commitment scheme using hash functions Let's say Alice and Bob are playing a game where Bob is trying to guess a number Alice has chosen.

Alice chooses a key $K$ and a number $N$ at random and performs $C=Commit(K, N)$ where $Commit(K, N)=h(h(K) \| h(N))$.
$h()$ is a collision-resistant hash function and $K$ and $N$ can be of any length.

Bob guesses $N'$ and sends it to Alice who responds with $K$ and $N$.

Bob can now do $C'=Decommit(K, N)$ which in our case is the same as Commit and verify that $C=C'$.

As I understand it the scheme above is perfectly hiding and computationaly binding. Is there a way to make the scheme both perfectly binding and perfectly hiding, or is there another scheme that has these properties?

I'm new to cryptography so I apologize in advance if I don't get some of the concepts right.

As you noticed correctly, a hash function is kind-of computationally binding if you assume collision resistance. However, it is impossible to achieve perfect hiding property for hash functions, due to the potential loss of information.

Perfect hiding means, that a computationally unbound Alice COULD decomit any value:
I.e. Pedersen commitments $c = g^xh^r$ can be decommited to any value, if you know the discrete logarithm $log_g h$.

In your hash function you have no guarantee for this: for a fixed pair of commitment and K there might not be $h(N)$ to fulfill the computation. Even replacing $h(N)$ with just $N$ does not imply this property.

In general, a scheme can not be both perfectly hiding and perfectly binding, because they are opposing principles: If Alice was computationally unbound, hiding means she can decomit ANY value, and binding means she could still decomit ONLY the original value.


Can an encrypted nonce be used for authentication? Would a scheme like the following work to allow authentication of a sender:

A nonce is appended to data, and the result is encrypted. The encrypted pack is sent to the other party. The sender then contacts the receiver through an authenticated channel (or one that is sufficiently good for the current purposes) and provides them with the nonce. When the receiver gets the encrypted file, they decrypt it. If the nonce matches the one given through the secondary channel, the encrypted pack is known to be from the sender.

Now, I realize no such scheme could provide non-repudiation, but the purpose in this case is simply to ensure that the encrypted pack has not been tampered with in transit. My presumption is that tampering with the encrypted pack without decrypting it has a high probability of creating gibberish, so the main threat of an MITM is the pack being removed and replaced with something else.

Does the approach above sound reasonable?

No. Whether your presumption is true depends on the properties of the encryption scheme you are using. In a block cipher's CTR mode, or virtually any other stream cipher, an attacker can arbitrarily flip any bit so desired, and those bit flips only affect the bits in question.  For block ciphers in CBC mode, a bit flip garbles the plaintext block in which the bit was flipped, but introduces another bit flip in the same position in the next plaintext block.

As you can see, errors do not necessarily propagate, unless the encryption scheme was designed for such, nor are they necessarily easy to catch. As such, I would recommend against the scheme you suggested.

Instead of generating a nonce, why not use that space to append a proper MAC, perhaps HMAC. Note that if you go with this approach, you should use a separate, independent key for the MAC.

Alternatively, use one of the authenticated block cipher modes. I'd recommend GCM, personally, but for more details, see Matthew Green's "How to choose an Authenticated Encryption mode". I recommend this approach, as it is quite difficult to mess up.


Approach towards anonymous e-voting I want to implement an internet-based e-voting system.
Voters shall be able to cast their vote for one out of n possible candidates. Each candidate has his own ballot-box kept by and at a trustworthy third party.
This third party is absolutely trustworthy insofar as it can be trusted to attend to his duties of supervising the cast diligently. However it is not without bias and hence under no circumstances must be able to see which voter voted for which candidate.

This problem can be approached using homomorphic encryption.
Votes are homomorphically encrypted and homomorphically added to the ballot-boxes.
In order to prevent the third party from gaining any knowledge of any vote cast every voter puts one vote into every ballot-box.
n-1 times this vote will be "0" for "no vote for this candidate" and only one time it will be "1" for "vote this candidate".

One unpleasant side effect of this approach is that the third party apparently is not able to check the correctness of every single vote.
A voter may try to give a "1" to more than one candidate or a "2" to a single one.
Of course the third party could hand out pre-signed voting coins in advance that the voters would use for casting their votes.
However the third party would recognize these coins, i.e. their values, and hence still know who voted for whom.

Do you have any idea how to solve this problem relying on as few possible other (trusted) third parties as possible?

Using exponential Elgamal as the encryption function,

Define the list of candidates: e.g., Alice, Bob, Carol
Voters submit an encryption of their vote: e.g., to voter for Alice: $v=\langle\mathsf{Enc}(1),\mathsf{Enc}(0),\mathsf{Enc}(0)\rangle$
Use an OR-proof (Fig 2) to show each ciphertext encrypts a 0 or a 1: e.g., $\langle \pi_1, \pi_2, \pi_3 \rangle$
Under encryption, add up the ciphertexts in the vote: e.g., $v_t=\mathsf{Enc}(1)\cdot\mathsf{Enc}(0)\cdot\mathsf{Enc}(0)=\mathsf{Enc}(1+0+0)=\mathsf{Enc}(1)$
Use the same OR-proof to show $v_t$ encrypts a 0 or a 1 (a 0 means the voter abstained)
Submit $\langle v, \pi_1, \pi_2, \pi_3, v_t, \pi_t \rangle$

Anyone can check the validity of $\pi_1, \pi_2, \pi_3$. Anyone can add up $v$ to see it is $v_t$. Anyone can check $\pi_t$.

The election officials take $v$ from everyone, add them up element-wise. Then the results are decrypted (usually with a shared key) using a protocol that proves it was decrypted correctly (see same paper for how to do this).


Rfc2898DeriveBytes - password length Trying to find related answer for a long time, but not convinced yet.

What I am trying is to encrypt using RijndaelManaged. To create Key, I am passing password, salt and iteration to Rfc2898DeriveBytes.

I was thinking to add constant if user entered password is below specific length before passing it to Rfc2898DeriveBytes.

So far what I found that adding constant will not add any benefit to security. Let suppose attacker get an access to database containing encrypted data along with salt, but not to constant will give him a bit harder time. Although in the end he will find that constant.

Or it is "really and extremely" safe to pass any length password to Rfc2898DeriveBytes without getting worried?

Does passing shorter or lengthier password affect key derivation process in term of which one is better and most recommended?

So far what I know that random salt and more iteration is important.

Following is the code, should I remove adding constant to password or keep it?

(Note: password length restriction to user is not applied at GUI, user can pass 1 character or even more than 10 characters)

string constant = "AnyConstantToMakePasswordBigger";

if (password.Length < 8)
{
  password = password + constant;
}

RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
byte[] salt = new byte[8];
rng.GetBytes(salt);
Rfc2898DeriveBytes derivedKey = new Rfc2898DeriveBytes(password, salt, 1000);
aes.Key = derivedKey.GetBytes(keyLength);
.....

Welcoming any positive or negative comment and responses.

There's no advantage to padding short passwords with a (non-secret) constant.

It doesn't make the password hashes any harder to crack by brute force guesswork: if an attacker can program a computer to try common passwords like abc, 123, swordfish, etc. (and they can, with very little effort), they can also just as easily make it try abcAnyConstantToMakePasswordBigger, 123AnyConstantToMakePasswordBigger, swordfishAnyConstantToMakePasswordBigger and so on.
It doesn't make the hashing algorithm (PBKDF2-HMAC-SHA1, according to CodesInChaos) any harder to break (not that anyone knows how to break it anyway).

In fact, technically, the HMAC-SHA1 algorithm does internally pad the password to 512 bits (= 64 bytes); it just happens to pad it with null bytes (and then XOR each byte with 0x36 for the inner hash calculation, and 0x5C for the outer one).  Note that, given the way SHA-1 and pretty much any other modern cryptographic hashes work, padding with null bytes is no more or less secure than any other fixed padding.

Padding the password with a secret constant (often called "pepper"), however, can improve security in some scenarios — specifically, if an attacker gains access to the password database (e.g. through an SQL injection vulnerability), but not to wherever the secret constant is stored.  However, if you want to do this, you should add the pepper to all passwords, not just to short ones.


Decode message $m = p * q$, where $p ^ 5 \bmod N$, $q ^ 5 \bmod N$ and $N$ are known I been going through some cryptography exercises and stumbled across this problem.

  Discover message $m$. You know that $m = p * q$. Also $p ^ 5 \bmod N$,
  $q ^ 5 \bmod N$ and $N$ are known numbers.

I am really lost and don't know where to start. Could anyone give some hints or point me to right direction where to read up on this problem?

I don't have a full answer yet but here is what I have so far.  Since you know what $p^5 \bmod N$ is and what $q^5 \bmod N$ is then you know what $m^5 \bmod N$ is. Since we also know what $N$ is then we should be able to find out how many times we need multiply $m^5 \bmod N$ by $m^5 \bmod N$ till we get a full cycle (you can calculate it through $\phi(N)$ or you can multiply by m till you get back to your original number).  From that cycle, go back 4 terms and that should be what $m \bmod N$ is.
Update: Finding $\phi(N)$ can be difficult for sufficiently large $N$ but multiplication with mods is a fairly easy cheap.  First make sure that N and 5 are relatively prime, and then (for practicality purposes) repeatedly iterate $F: x\mapsto x^5\bmod N$, starting with the known $x_0=m^5\bmod N$ until $x_{j+1}=x_0$, thus making $x_{j}$ a possible $m$


Time complexity of Weil pairing I ran and timed an implementation of the Weil pairing on three set of parameters. One with an order of 512 bits, one with 256 bits and the last with 161 bits.

I took the Miller's algorithm to compute the Weil pairing. The algorithm that I used for the multiplication of 2 points is the double-and-add. Both algorithms have a time complexity of $O(log (n))$ if I understood correctly.

The time I got was 10 seconds for 512 bits, 2,5 seconds for 256 bits and 1,1 seconds for 161 bits. When I see the time I got it seems more like a complexity of $O(n^2)$ or $O(n \cdot log (n))$.

Can someone tell me what the time complexity is based on my results?

Miller's algorithm is a loop over the group size; let's say it has $n$ bits. (The group size is usually near the prime $p$ of the underlying field)

Each iteration of the loop computes a point doubling and maybe a point addition, and a bunch of field multiplications (or squarings). That sets a upper limit of a constant number of field multiplications in each iteration. The complexity of naive multiplication is $O(n^2)$; with Karatsuba it is $O(n^{\log_2{3}}) = O(n^{1.585})$. Therefore that's the complexity of each iteration.

Thus, since there are $n$ iterations, the complexity of Miller's algorithm is $O(n^3)$ with naive multiplication and $O(n^{2.585})$ with Karatsuba.


Conditional probability with Vigenere Cipher given specific plaintexts and key sizes Apologies if this should be in the Mathematics stack exchange, I just ask it here because the context is cryptography. Here is the question that I seemingly cannot get correct:

  Consider the Vigenere cipher over the lowercase English alphabet,
  where the key can have length 1 or length 2, each with 50%
  probability. Say the distribution over plaintexts is Pr[M='dd'] = 0.2
  and Pr[M='de'] = 0.8. What is Pr[C='ff']?

My starting assumptions are therefore that:

Pr[M=dd]    = 0.2
Pr[M=de]    = 0.8

I believe I can calculate Pr[C=ff] in the following manner:

Pr[C=ff]    = (Pr[C=ff | M=dd] x Pr[M=dd]) + (Pr[C=ff | M=de] x Pr[M=de])

From a notation point of view:

M = message
C = ciphertext
K = key
Pr[M=dd] = Probability that the message is 'dd'
Pr[C=ff | M=dd] = Probability the ciphertext is 'ff' conditioned on the message being 'dd'.

The convention for key notation is that:

K=a means 'shift by 0'
K=ab means 'shift first character by 0, shift second character by 1'
etc.

So:

For key length 1, M=dd: There is only one key that can produce C=ff (that is K=c).
For key length 2, M=dd: There is only one key
that can produce C=ff (that is K=cc)
For key length 1, M=de:
There is no key that can produce C=ff.
For key length 2, M=de:
There is only one key that can produce C=ff (that is K=cb)

Therefore:

Pr[C=ff | M=dd] x Pr[M=dd] = [1/26 + 1/(26^2)] x 0.2
Pr[C=ff | M=de] x Pr[M=de] = [0 + 1/(26^2)] x 0.8

Ergo:

Pr[C=ff] = [1/26 + 1/(26^2)] x 0.2 + [0 + 1/(26^2)] x 0.8
Pr[C=ff] = 0.009171598

Apparently this is incorrect, but I'm not sure where I'm going wrong, can anyone help explain what I'm doing incorrectly?

The answer to this (thanks to help from fkraiem) was literally included in the first sentence of the question.

I went wrong by assuming that the probability of the occurrence of a 1 or 2 character key didn't weigh into the calculation. My (rather questionable) reasoning was that since the key did in fact have to be either 1 character or 2 characters (i.e. it couldn't be 0 or 3 or more characters), that the 50% probability didn't weigh into it. Yes, that reasoning is in fact both as silly and as incorrect as it sounds.

So, the corrected components of the calculations above are:

  Therefore:

  Pr[C=ff | M=dd] x Pr[M=dd] = [1/26 x 0.5 + 1/(26^2) x 0.5] x 0.2
  Pr[C=ff | M=de] x Pr[M=de] = [0 x 0.5 + 1/(26^2) x 0.5] x 0.8

  Ergo:

  Pr[C=ff] = [1/26 + 1/(26^2)] x 0.5 x 0.2 + [0 + 1/(26^2)] x 0.5 x 0.8
  Pr[C=ff] = 0.004585799


Is XORing a SHA256 better than truncating it? Let say I want to truncate SHA256 to 128 bits. What would be the best way to minimize a probability of a collision and improve collision resistance?

Taking the last 16 bytes
Taking the first 16 bytes
XORing the first 16 bytes and the last 16 bytes together

And should I assume that the same logic will apply for other hash functions from the SHA-2 set (like SHA516) as well as other hash functions in general, for example, SHA-1 or MD5?

As pointed out in an answer to an older question, SHA-224 is more or less just using the first bits of the output of SHA-256. That is just about the most official construction anyone can find.

The XOR approach is however not entirely unprecedented, for example Linux uses that approach on SHA1 in order to generate random bits.

There is real security to be gained by not using either approach, but instead use a cryptographic hash to reduce the 256 bits down to 128 bits. This would provide protection against length extension attacks.

Also worth noting is that on 64 bit architectures SHA-384 and SHA-512 are both faster than SHA-256. So you may in fact get a faster and more secure result by computing SHA-512 and then reducing that output down to 128 bits using another hash.

I do however not know which hash could be recommended for reducing the output from 256/512 bits to 128 bits.


What makes SHA-2 and SHA-3 have security levels half their output hash length? The tag wiki for sha-256 says, in part:

  SHA-256 ... processes the input in 512-bit block and has a 256-bit output, for a 128-bit security level.

I'm not a cryptographer, just an interested amateur, but how does it follow that SHA-256 has only a 128-bit security level? (More generally about the whole SHA-2 and SHA-3 families.) Also, against what type of attack is this considered?

I looked to Wikipedia which didn't really help my confusion. The cryptanalytic results listed (up to 2014) are all for reduced-rounds variants, and most for SHA-256 are on the order of $2^{250}$ complexity or more. The comparison of SHA functions gives the security of each SHA-2 and SHA-3 family function as half the output hash length, but provides no clarification of how this figure is derived.

Is the security level related to the relationship between the input processing block size and the output hash length?

Please go easy on me with the math; plain English explanations backed up with some math are preferred.

You can't say SHA-2 has a security level of half its hash length without any given context.  128 bit against what type of attack?  What is the attacker trying to do?  Perform a collision? Ok yes it has 128 bit against collisions. Perform a preimage? Nope it has 256 bit security against preimage attacks.

Any algorithm is considered n bit strength if the expected number of operations for the average case is 2^n.  For unbroken cryptographic hashes the strength is 2^(n/2) against collisions and 2^n against preimages.  Collisions are simply "easier" than preimage attacks due to the birthday problem.  They take less operations so you need a larger search space (digest length) to achieve the same level of security.

So the statement that SHA-256 has 128 bit security is incomplete and it ignores the fact that collisions are not always relevant.  Against many type of scenarios a collision is of no value.  An example where collisions are not a threat would be hashed passwords.  For an attacker to break a specific password they need to find a preimage of the password hash.  In that application SHA-256 has 256 bit security because collisions present no security risk(i.e. attacker determines abc and xyz both hash 1234 and that doesn't match any password hash).  It doesn't help that the word collision is used in common language to scenarios which refer to a preimage.  Also keep in mind there are two types of preimage attacks and once algorithms become partially compromised they may have differing levels of security depending on if it is a first or second preimage attack.  Of course once an algorithm is compromised you should look to migrate to a more secure algorithm but that distinction could be relevant in some situations.


Specification of the scream stream cipher is unclear I am implementing in C++ the Scream stream cipher. The Scream family is composed of Scream-0, Scream-S and Scream-F. For this question, assume that I'm using Scream-S.

The specifications of the Scream cipher are given in the paper "Scream: a software-efficient stream cipher", but  I didn't find a reference sourcecode for this cipher which could have helped me.

Maybe because the specs include many notations, I have some questions about the scream cipher:

In section 2 about the two 2X2 matrices : Am I right to say that $x$ and $x+1$ (from the $GaloisField(256)$) are replaced respectively by $2$ and $3$?
In section 3, it's possible to implement the function $F$ to optimize it. The author didn't define the multiplication ($u0 = M1(0,0) . S1[x]$). Is it a multiplication following $GF(256)$ with the polynomial $x^8 + x^7 + x^6 + x + 1$ (0x1C3) ?
In the algorithm of $F$ in section 3, they write 'byte0'. Does $byte_0$ refer to the MSB or LSB of an integer ?

Since $F$ is the core of the algorithm, it's important for me to know and understand these kind of details.

I've just dived into that paper for you, with the following results:

You've got that one correct.
The eight-byte input is multiplied with matrix M. There is no mention or indication of the polynomial you mention. Simply follow the paper.

The matrices are fixed [[1,2],[2,1]] and [[1,3],[1,3]]. So, 2 and 3 are NOT replaced by x. The multiplication is on GF(256) with the polynomial specified at page 4. Thus, you have to do something like this: GF256_Multiply(2, S1[x], 0x1C3) where 2 = M1(0,1) = M1(1,0) for example. That's why they call T0 and T1 "lookup tables". These are fixed tables which imply M1 and M2 are fixed too.

(Notice: This was corrected thanks to OP's own research and the corrections OP mentioned in the comments to this answer.)
I think you got a bit confused there. MSB (= Most Significant Bit) and LSB (= Least Significant Bit) define "bits", while the paper explicitly talks about "bytes" in section 3. Therefore, they did not need to define any MSB or LSB. The paper simply defines $byte_0$ (which is, reading from left to right, the leftmost byte), and $byte_3$ (which is the rightmost byte). So you practically extract the 4 bytes into $byte_0$ up to $byte_3$ from left to right (aka "first in, first out").

Hope that helps.


How much safer is RSA-OAEP compared to RSA with PKCS#1 v1.5 padding? Is there a way to calculate how much safer RSA-OAEP is compared to RSA with PKCS#1 v1.5 compliant padding? Or is there a good rule of thumb?

RSA PKCS#1 is still secure if padding oracles do not apply. If padding oracles apply, for instance when a server verifies the padding after decryption and somehow leaks the result (through an error message or by leaking information about the the verification time) then OAEP is much more secure.
Note that in principle OAEP can also leak information through timing attacks, so just using OAEP is no panacea.

[EDIT] Another problem with PKCS#1 v1.5 is that it allows for a relatively small amount of randomness - 8 bytes in the range 1..255 - to be used for larger messages. This can be avoided by using hybrid cryptography (where a symmetric cipher actually encrypts the message) or simply by using smaller messages. However, the MGF1 function of OAEP should be better protected against abuse.

Furthermore, OAEP also has a security proof that the padding should be secure as long as RSA is deemed secure. Although there are no known attacks on PKSC#1 - besides the aforementioned padding oracle attack - the algorithm doesn't have a formal security proof so it is possible that attacks do exist.

These kind of things cannot be easily quantified. RSA has about no security if PKCS#1 padding oracles apply. The lack of security proof may lead to an attack in the future, but this is - very likely - independent of the key size. Neither calculations nor rules-of-thumb apply. You should rather take a good look at your use cases, threat-model and attack  vectors.

Or just use OAEP. Many libraries support OAEP because PKCS#1 is deemed less secure. Using RSA-KEM would also be a good option if that's available to you (and it is relatively easy to create if you have raw RSA available).


Should I calculate two CMACs over two different strings that share common bytes? I am trying to secure my RF communication in which one RF package consists of two separate segments. I need to make sure that one segment of one packet is not replaced with a valid segment of some previous packet, if you know what I mean.

My RF packet is 32 bytes long, and I need to secure it with CMAC (I found an implementation of AES-128 in CBC mode and CMAC - operating on 16 byte blocks). I am planning on doing it like this:

[B1][B2][B3]...[B30][B31][B32] = bytes in my RF packet

[B1] [B2]... [B10] = first segment (10 bytes long)
[B11][B12]...[B20] = second segment (also 10 bytes long)
[B21][B22]...[B32] = remaining bytes of RF packet contain CMAC of first segment,
                     and CMAC of second segment (both truncated to first 6 bytes
                     in order to fit into 32 bytes that I have for one transmission).

Now for the problem: In order to make sure that nobody captures two of my RF packets, and creates third new packet that contain fist segment of packet 1 and second segment of packet 2 (with corresponding CMACs also copied) I am planning on calculating CMAC of first segment + 6 bytes of second segment, and calculating CMAC of second segment by borrowing last 6 bytes of first segment and remaining 10 bytes of second segment.

Should I do this? If not, how can I make sure someone doesn't transmit third custom packet containing two valid segments of my previous transmissions? It would be best if I could somehow calculate CMAC on the entire 20 bytes, but as I know I can only work with 16 byte blocks maximum.

By using 6-byte MACs you can only authenticate about $2^{24}$ messages on average before seeing a collision, which would allow an attacker to swap one message for another. There's a decent chance you'll see one much earlier, so in practice you can only safely use a key for some thousands of packets.

So the best option would be to find an implementation of CMAC (or another secure MAC, like HMAC) that allows you to create a single 12-byte authenticator for the whole 20-byte message.

If you do need to go with the 16-byte CMAC implementation for some reasons, I think including the first MAC as part of the second message is better than overlap, which may be shared between two messages. I.e. calculate the second as $MAC(B[11]...B[20]||MAC(B[1]...B[10]))$. You would still be limited in the number of messages you can send before collision.


Where is the SIV in AES-GCM-SIV? This is my understanding of Synthentic IVs
You have 2 keys $K_1$ & $K_2$.
$F$ is a PRF
Instead of choosing a separate IV, you instead generate the IV from the PlainText.
$IV = F(K_1, m)$
$c = E(K_2, m, IV)$
You don't need a separate Tag/Hash for authentication. Because the IV is generated using the PT  itself, after decrypting the CT, you can generate the IV at the decryption end & check it it's same as IV send along with the CT.
I was looking at AES-GCM-SIV - https://tools.ietf.org/html/rfc8452
Here the IV seems to be passed as Input to the Encryption Algorithm & is not generated from the PT.

AES-GCM-SIV encryption takes a 16- or 32-byte key-generating key, a 96-bit nonce, and plaintext and additional data byte strings of variable length.

It also seems to produce a tag

Calculate S_s = POLYVAL(message-authentication-key, X_1, X_2, ...). XOR the first twelve bytes of S_s with the nonce and clear the most significant bit of the last byte.  Encrypt the result with AES using the message-encryption key to produce the tag.

So why is this Encryption named as an SIV scheme?

The SIV that you describe is the way that it is often specified specifically for key wrap. However, you always want to have an IV since encryption of the same message twice should yield different ciphertexts. If you only derive the IV from the message and key, then it will always be the same for the same message. By deriving the effective IV from the input IV, message and key, you guarantee that different messages and different IVs always give different ciphertexts, and the only "flaw" is when the same message is encrypted twice with the same IV (and in this case, only that fact is revealed). This is optimal nonce-reuse resistance.
Note that an IV is input to AES-GCM-SIV, but it is used to derive an "effective" IV from the tag, that is actually used to encrypt the message. The continuation in the RFC that you quoted is "The encrypted plaintext is produced by using AES, with the message-
encryption key, in counter mode (see [SP800-38A], Section 6.5) on the
unpadded plaintext.  The initial counter block is the tag with the
most significant bit of the last byte set to one." (Note that the initial counter block is the tag...)
AES-GCM-SIV also does continual key derivation from the input IV in order to get better security bounds. However, that is an orthogonal issue.


How much stronger is RC4 if it is keyed with an RSA private key? My idea is to generate a RSA 2048 bit key and use RC4 with the private RSA key to encrypt a stream of data. RC4 is weak because RC4 keys are small, 256-bit. But when we use RC4 with private RSA 2048 key, how much stronger will it be?

RC4 has several known weaknesses, including:

Rather strong biases in the initial parts of its keystream
Weaker biases in the rest of the keystream.

Now, RC4 does take a variable length key, potentially up to 2048 bits (256 bytes).  So, if you wanted, you could take a 2048 bit RSA modulus, and use that as the RC4 key.  However, doing so would not affect most of the known biases; these occur independent of the key size.  What RC4 does internally is effectively take the key it is given, and repeat it until it has something 256 bytes long (and uses that to stir the initial permutation).  Most of the biases do not occur because of repeats in this expanded key, and so are unaffected by a larger key.

Now, I say "most of the biases" because there is one bias in the initial keystream that would be cleared up by a larger key; a 32 byte key would cause a bias at locations 32, 64, 96 (and gradually dying out until you hit location 256); a larger key would eliminate that bias.  However, there are plenty of other biases in the initial keystream; just eliminating this one doesn't solve the problem.


What are alternatives to number theory based crypto? Quantum crypto,lattice based crypto, Neurocryptography and cellular automata based cryptography are alternatives to number theory based crypto. I need to know what are the other hard problems like Lattice problems and Number theory based problems that can be used for cryptography(For asymmetric crypto).

Code based cryptography like McEliece cryptosystem, is based on the hard problem of decoding linear codes. But i think it lies to the group of quantum based crypto since as far as we know it is still immune to quantum attacks


SHA-512 Encipherment via CBC I wrote a cryptographic function that encrypts a plaintext by using a series of SHA-512 hashes that are used to encrypt the data via a simple byte-to-byte XOR. In order to prevent various attacks, I implemented CBC by hashing the current hash value and the previously enciphered block together. That resulting hash is then used to encipher the next 64-byte block of plaintext via simple XOR. The initial key is a SHA-512 hash of the passphrase or other key. I added several thousand rounds of hashing, and I still need to implement a random 64-byte pad to the front of the code to eliminate some guessing, but as a method is this a sound approach?
I can't imagine it being incredibly insecure, but I am interested in the methods one would use to crack the code.

If the adversary has the plaintext for a block, then the "current hash" can be calculated by simply performing XOR with the ciphertext block at the same position.  In that case, every block after that can be decrypted as the "current hash" and the "previously ciphered block" are now known. So the scheme seems to fail for a known plaintext attack, and is thus not IND-CPA secure.

That or "the current hash" has a meaning that you haven't told us about.


Can I reuse a nonce to retransmit the same packet using ChaCha20-Poly1305? I understand the "sudden death" implications of reusing a nonce with ChaCha20-poly1305, but I believe this rule doesn't apply if you are transmitting exactly the same packet.

I'm putting together a small radio protocol where packets can be lost and if an ack isn't received the packet is re-transmitted. In this instance the nonce is reused, but I can't see that an attacker has any more useful information than the initial packet. I would presume that the key is still safe. Is this correct or have I missed something obvious?

EDIT:

It is a custom protocol, based on a resource requirement that prevents going with something like 6LoWPAN.

I was not going to use random nonces, but rather sequential nonces, with the top 32 bits of the 96 bit nonce set to the 32 bit node address that the packet comes from. The problem with this is reliably storing the nonce in flash with limited erase / write cycles. Although I have seen implementations save blocks of nonces, rather than every use.

I can gather entropy from concatenating the lowest bit of multiple reads of the signal strength from the radio, but I would guess that sequential nonces are safer to use, if I can guarantee they are sequential.

I was thinking of using a network registration method where the node, on power up, would have a preshared RX encryption key, but no TX encryption key. The node would ask for network registration where a master node (server) would send a new TX key encrypted and authenticated. If correctly received the new node would use the new TX key and the nonce would start again from 0. This would get around the problem of storing the nonce at the expense of a slight delay in network registration. This network is only designed to be local to a single site, all nodes within reception of each other.

I understand the "sudden death" implications of reusing a nonce with ChaCha20-poly1305, but I believe this rule doesn't apply if you are transmitting exactly the same packet.

There are two aspects to consider here: (a) confidentiality (can an adversary find out anything about the content of the plaintexts) and (b) authenticity (can an adversary forge packets).  On the confidentiality front you're unquestionably right.  A passive eavesdropper doesn't learn anything new about the plaintext from seeing the same ciphertext twice.

On the authenticity front I think it's trickier, and no verdict should be reached without careful analysis.  It's safe to say that authenticating the same message twice with the same nonce doesn't allow the adversary to easily forge any other message, so you're certainly not violating the authenticated cipher's rules.  But you do need to think about how this fits in the bigger picture—the protocol level above the cipher level.  I would ask myself, for example, whether there are scenarios where an active adversary could defeat some security property by replaying a packet they've eavesdropped on a second time, or suppressing the reception of packets and then feeding them to the recipient out of order.

Protocol design is tricky.  Authenticating individual messages doesn't automatically guarantee authenticity of a sequence of interactive session of messages.


What makes LSBit steganography detectable? And what would help in concealing it? In a project of mine I took a 24-bit bitmap image and I performed LSBit steganography over it (saved a black and white image inside each of the planes R, G, B) using pixel shuffling and xor encryption.

Is my stenography easy to detect? And what would it take to conceal it?

A general theoretical answer to the title's What makes LSBit steganography detectable? is that in normal images, the LSBit of a pixel in some channel is correlated to higher-order bits in the same pixel and channel, that pixel in other channels, and adjacent pixels, in ways that mere replacement of LSBit tends to strongly alter.

One simple way to improve that is adding noise or blurr to a degree such that the LSBit is nearly indistinguishable from random, in which case it can then be replaced by something equally indistinguishable from random (as resulting from good encryption) with little chance of detection versus an equally noisy/blurry image. Next step is changing only few bits at locations dependent on a key (towards that goal it is necessary to have a small payload, as previously pointed), and have the other pixels randomly noisy according to a good model of the natural image.

From a practical standpoint, sending uncompressed 24-bit bitmap images somewhat is a red flag that basic stego is in use. That would be somewhat less apparent with an additional step of JPEG lossless compression, or PNG or GIF conversion (lossy compression would destroy the hidden message given the LSBit encoding used; more sophisticated stenographic schemes survive that). Notice that sending noisy/blurry images without lossy compression is a waste of bandwidth, and could also raise alarm.

I suggest two "easy to detect" tests, to be applied comparatively on your image with stego (after decompression if a lossless compression step is added), and normal images that could be allegedly sent, at least including the one you start from.

Show as an 8-color image the 3 LSBits of each pixel; that can be done by changing each byte x in each RGB plane to ~((x&1)-1). It there something perceptibly remarkable for your image with stego? Update: a 64 or 512-color image using (x<<6)+32 or (x<<5)+16 might also be interesting. (note:  the three expressions are for C, and assume truncation to octet. ~((x&1)-1) yields 0x00 if the low bit of x is clear, 0xFF otherwise).
Is the compression ratio of PNG markedly lower for your image with stego than for normal images?

Note that these tests can only demonstrate failure to be undetectable.


Argon2 for both password storage and key derivation Is using Argon2 for both password storage and key derivation secure? I'm planning on using different salt values, of course.

The basic concept is something like this:

Alice has some secret data ($data_e$) on her account. It's encrypted with an Argon2 derived key from her password, using a random salt.

$$ k = \operatorname{Argon2}(\text{password}, \text{salt}_1, \text{iteration})$$
$$ \text{data}_e = \operatorname{E}_k(\text{data})$$

Alice's password is stored as an Argon2 derived key from her password, using a random salt. When Alice (or an adversary) wants to log in, a key is derived from the input using Alice's password salt and checked for a match.

$$\text{storedPWD} = \operatorname{Argon2}(\text{password}, \text{salt}_2, \text{iteration})$$

Should the secret data be encrypted with Alice's raw password?
Should her data to be encrypted with a random key encrypted with her raw password? With a key derived from her password?

You should assume that Alice is a trained system administrator who understands the risk of having a weak password. The password will have at least 12 characters, will include capital and small letters and have numbers.

Also assume that the login system is bruteforce-resistant, but think about the possibility of a database breach.

Thanks in advance.

Should the secret data be encrypted with Alice's raw password?

As a general rule of thumb:
A password should only ever be fed into a password hashing scheme (PHS) such as Argon2, scrypt or bcrypt, never into anything else!

There are multiple reasons for this:

Passwords need special processing in the form of complexity parameters.
Passwords need external (high-entropy) sources of uniqueness / randomness to be mixed in.
Passwords should be allowed to be long and variable-length, most cryptographic primitives have very specific expectations on key lengths.
Passwords usually aren't randomly uniformly distributed bit strings (eg the highest bit is rarely set), which most encryption algorithms assume for their keys.

  Should her data to be encrypted with a random key encrypted with [...] a key derived from her password?

Yes. Another good rule of thumb is:
Only ever perform one password hashing per user, but give it all the resources you can spare.

The idea behind this is:

If you chain derivations and an attacker can validate whether they got the correct value for an intermediate stage, they only need to compute the last stages once, instead of once for all passwords.
If you don't expose intermediate values, you effectively created a new composite hashing scheme.
If you perform two independent derivations, you are likely to lower the resources required for each individual one and it is sufficient for the adversary to only break the weakest one and get the other one(s) "for free".

The rest is similar to smrt28's answer:

Encrypting a high-entropy key with a password-derived key allows your users to change the password without you having to re-encrypt the entire data, which may be costly in terms of CPU-time and I/O-time if you have a lot of data.

Additionally, if you use authenticated encryption (AE) using the derived key for the high-entropy key, you essentially get secure password confirmation "for free", as the scheme will very clearly report an error if the password and thus the derived key is wrong. Additionally, you can cryptographically bind derivation parameters like salt and iteration count to successful decryption using the associated data input of most AE schemes.
So in formulas: $\text{derKey} = \operatorname{Argon2}(\text{password}, \text{salt}, \text{iteration}), c=\operatorname{AE}_{\text{derKey}}(\text{MK})$ and now if one tries to decrypt with the wrong password, the AE-scheme will report an authentication failure as the key is wrong and if it is right, it will just return the correct master-key.


Is it possible to determine public key if you know private key? Is it possible to determine public key if we know private key?

Employees has RFID card and RFID is a private key for employee.

I want to encrypt some user's (employee's) data with employee's public key, but I don't want to anybody read encrypted data without employee's RFID card.

My idea is that If we can use some function which will create public key based on RFID as a private key, than we can store that public key in rest of data of employee so encrypted data can be read only if we have RFID private key.

Is this possible and which function are you suggest?

Since you tagged the question with "rsa": Yes, with rsa it would be very easy to determine the public key (n) from the private key (p & q), because n = p * q.


File using same key on XOR cipher. Using CBC I have some files that are encrypted using an unknown key and it's using the CBC method to encrypt the files.

When I XOR two files together the first two bytes are always the same, but different for each files (make sense for each file)

From that is it possible to recover the real key?
First bytes of the file :

1a 1a 14 54 08 0b 02 59

When xoring it to a another file using the same key the first few bytes are :

3a e5 1f 01 3a e5 1f 01

Another beginning of xoring with different file

bf fb 22 10 bf fb 22 10

As you can see the pattern repeats for those only 8 bytes. It does that for every file that I xor. Does that mean the key length is 4? And from that how can I recover the text ?

The "XOR cipher" described does not encrypt more than the first block, even if you do not reuse keys. The subsequent blocks can be "decrypted" by the attacker simply by undoing the XOR – there is no secret involved.

Decrypting the first block and finding the key does require more than one message. It is a case of the many-time pad and can be solved either using a known plaintext or by crib-dragging as described in the link above.


Hash based code obfuscation? The code

if(str1 == "abc") {}

can be converted to

if(hash(str1) == 0x8732e) {} // assume hash("abc") == 0x8732e

to obfuscate the code.

But they are not equivalent when hash collision occurs; e.g., another string xyz's hash value is the same as abc.

That is true theoretically. But is it an issue in real-life when the method above is used to obfuscate code? Is it a well accepted obfuscation method?

Edit: after a little research, I guess what I need is a one-way collision-free string transformation function, as I don't care the length of the output. Any suggestions? Any mature implementations?

If the inputs you're hashing aren't long enough with enough entropy, the hashes can be inverted by an adversary who is willing to brute force the entire range of possible inputs.

For example, hashing abc provides little barrier to those who are dedicated at deobfuscated your program, as it takes almost no time to calculate hashes for all possible 3 character strings.

The adversary can build a table of all inputs up to a certain size and proceed to crack your obfuscated data in negligible time. If your adversary has financial motivation, this probably will not protect your code.

You could opt for additional protection by using slow, salted hashes, which are usually employed to protect passwords. Using a salt can prevent your adversary from precomputing the table before he has access to your source code. The downside is that using a slow hash in an effective manner will cause a non negligible performance hit to your application.


Hashing with (some sort of) Public and Private keys/salt/nonce I'm trying to design a protocol where hashing can involve some public and private components.
The idea is that Alice hashes a value with minimal computation and sends the hash to Bob.
For Bob it should be exponentially harder to re-create / verify the hash against a given value with the hash he received from Alice.

The hash function Alice is going to use will be something like this, with constant time:

$$H_A = \text{hash_generate}(\mathit{input}, \mathit{private\_component}, \mathit{public\_component})$$

The hash / verification function Bob is going to use will be something like this, with exponential time:

$$\text{hash_verify}(H_A, \mathit{input}, \mathit{public}\_component)$$

What I have devised is the following:

This is what Alice does, (this is constant time)

Alice creates random $n$ bits as $\mathit{public\_component}$
Alice creates random $n$ bits as $\mathit{private\_component}$
Alice salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component} \mathbin \| \mathit{public\_component}))$
Alice sends the $\mathit{public\_component}$ and the hash result $H_A$ to Bob

And what Bob does in order to verify is the following:

Bob creates random $n$ bits as (replacement) $\mathit{private\_component}^{rand}$
Bob salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component^{rand}} \mathbin \| \mathit{public\_component}))$
If the hash result is the same as Alice's hash result, he has verified it
If the hash result is the not same as Alice's hash result, goto 1 (or fail with a given repeat count based on $n$, guaranteeing we have done enough permutations to prove that we can't verify the hash)

So the expected complexity of Bob's operation should be around $\mathcal{O}(2^n)$

This protocol is what we have came up with; it's similar to proof of work in a way.

Are there protocols for such a use-case? If yes, how are they called?

What you are describing here looks like a thing, indeed. For instance, in the case of passwords, you have human-created password, whose entropy is generally weak and who are often found in dictionaries...

So, suppose you'd like to store the user's password in your database in a way that would prevent an attacker obtaining the database to deduce the actual password used by any given user, the simplest way around it might be to simply hash the passwords and store the hashes, right?

Well, if you just hash the passwords, then an attacker could simply take a dictionary and hash its content and compare it to the hashes he found in your database... So it wouldn't prevent the adversary to possibly find some passwords.

So, the next step is obviously to salt the hashes you are storing, in order to increase the cost of the dictionary attack for your adversary. And you can even use a different salt for each password, thus increasing the cost of a dictionary attack even more.

Note that modern hash functions, such as Blake2, sometimes includes support for salted and even for keyed hashing out of the box.

Modern password hashing algorithm, such as Argon2 are actually very similar to "proof of work", as you noticed, since you want to make your adversary consume as much time and power as possible.

There are also other cases where you'd want something like this (see how HMAC works, for instance.)


How do we find the last two correspondences in an otherwise known even permutation? A secret even permutation $P$ of the set of non-negative integers less than $n$ is chosen. That might be a Feisltel cipher with a random key.

We are given in sequence the $P(x)$ for $x$ from $0$ to $n-3$, and must output the ordered pair $(P(n-2),P(n-1))$.

What's an efficient online algorithm for that? What’s a practical minimum for the memory needed?

What if we are allowed $n-2$ queries giving $P(x_i)$ for any $x_i$ that we iteratively decide, and must output $(x_{n-2},P(x_{n-2}),x_{n-1},P(x_{n-1}))$ where $x_{n-2}$ and $x_{n-1}$ have not been queried?

What if we are allowed to repeat an earlier query for free?

All permutations have a cycle decomposition from which you may immediately read off your $P(n-2)$ and $P(n-1)$.  There are trivial algorithms for doing this that run in either $O(n)$ time and $O(n)$ space (invert the permutation), or $O(n^2)$ time and $O(1)$ space (walk backwards by querying everybody repeatedly).

You could adapt that invert the permutation algorithm to use only 1 bit per element, but that's still $O(n)$ space.  Alternatively, if you have an efficient representation for a sparse permutation, then you may replace $n$ by the number of elements actually moved.

In general, inverting a permutation is [exactly] as hard as unordered search.


Does IKEv2 protocol have two modes like IKE IKE Protocol have 2 modes, that modes have different structure. Does IKEv2 protocol have two modes like IKE.

No, IKEv2 has nothing analogous to 'main mode' and 'aggressive mode', and they eliminated the initial 'quick mode',

When IKEv1 was originally written, they wanted a strong separation between IKE and IPsec; they had a vision where IKE might be used for things other than IPsec (other "Domains of Interpretation").  So, they completely isolated the "negotiate IKE SAs" and "negotiate IPsec SAs" into two separate series of exchanges.

In addition, they weren't sure if it would be better to minimize the number of round trip messages, or to provide identity protection; hence they designed two different modes (which would allow implementers to select the trade-off).

When they designed IKEv2, they rethought both these options.  They realized that no one really used IKE for anything other than IPsec, and that forcing implementers to support different options was the Wrong Thing.  Hence, they tried to combine the IKE SA and initial IPsec SA negotiation into a single set of exchanges (reducing the number of round trips, hence getting most of the benefit of "aggressive mode"), while retaining the identity protection (and DoS resistance) of main mode.


Can Microsoft's SIDH (Supersingular Isogeny) keypairs be reused for encryption? If not, why? I was considering using Microsoft's SIDH implementation for post-quantum public-key encryption because of its relatively small key size. I realized however, thanks to Issue #4, that it might not be as ideal as I had hoped:

  SIKE is IND-CCA2 secure, which means that it's ok to reuse the key pair generated [...] whereas SIDH is insecure with re-used keys [...]

So here we go:

Is SIDH actually insecure when keys are reused?
Is SIKE actually secure even when keys are reused?
If so, why? How can SIDH actually be broken? Can you demonstrate an attack?
What prevents an attacker from encrypting many messages with a SIDH public key and breaking it that way?
What's the difference between the two that makes it so one can securely use reused keypairs and one can't?

Is SIDH actually insecure when keys are reused?
  If so, why? How can SIDH actually be broken? Can you demonstrate an attack?

Yes it is. There is a well known adaptative attack, described here https://eprint.iacr.org/2016/859

  Is SIKE actually secure even when keys are reused?

Yes it is. There is a security proof, assuming the number-theoretic hardness assumptions SIDH is based upon are true.

  What prevents an attacker from encrypting many messages with a SIDH public key and breaking it that way?

That's the definition of CPA security. SIDH is proven CPA secure.

The CCA attack works by generating faulty ciphertexts (not plaintexts) and sending them to a decryption oracle. The attacker learns something on the key by observing whether decryption succeeds or not.

  What's the difference between the two that makes it so one can securely use reused keypairs and one can't?

SIKE uses a generic transformation meant to turn a CPA secure protocol into a  CCA secure one. Essentially, it amounts to recomputing Bob's public data to check that he did not cheat in computing the ciphertext. This thwarts the attack, and indeed also any other potential CCA attack.


Should I use “modes of operation” for a single block of data? I am using AES to encrypt my data. I have only 128 bit block that I am encrypting using AES. I am using AES in CTR (counter) mode, since it is always to advisable to use block ciphers along with modes of operation… but I think this is generally the case when you have more than one block of data.

Should I also be using AES in Counter mode to encrypt a single block?
And does AES of single block in CTR mode enhance my confidentiality?

Even though you are only encrypting one block at a time, think about what would happen if your input data happens to be the same as a previous encryption.  Even though you are encrypting the blocks days or weeks apart, plain encryption (aka ECB mode) would have the same problems as usual.  Counter/CBC/... are designed to avoid that problem.  If you know the input data won't repeat (sequence number, etc. as part of your data) then you won't have the repeating blocks problem of ECB where identical plaintext, when encrypted with the same key, always outputs the same ciphertext.


Combining two hashing functions I have been working on a Bloom Filter implementation recently and after a discussion with a co-worker about how many hashing functions to use I told him I was limited with using hashing functions that are already implemented and didn't want to risk the loss of distribution if I derive hashing functions from them.

We can assume that the distribution of any hashing function is not 100% perfect. It's very good for many, but not perfect. Is there any existing literature that describes the loss of distribution? I am not using the hashing functions for cryptographic purposes directly, because in a bloom filter it's only used as an index, and it's the distribution is the most important for my needs - but I assume they are related.

For the purposes of a bloom filter you need a number of hash functions. Cryptographic hash functions are designed so that changing a single bit in the input should change many (around 1/2) of the output bits.

So, say you have a good hash function $h$ (e.g., SHA256 though MD5 should work for your purposes too) a good option for you would be to use use:

$h_1(m)=h("1" || m)$
$h_2(m)=h("2" || m)$
$\vdots$
$h_n(m)=h("n" || m)$

Where $||$ is concatenation. Then you only need one hash function. This is basically what they are doing in this java implementation.

  Is there any existing literature that describes the loss of distribution?

Not that I am aware of. But think about it this way, if there were a significant change from the uniform distribution computable in a reasonable amount of time we wouldn't use the hash function for cryptographic purposes.

Now, is there some sort of attack you are worried about?


Checking if a sentence is English after decryption I wrote a program that will loop through the anagrams of a word and run each one through the decryption of a columnar transposition cipher on a document. However, for a certain word, the number of anagrams was 7! (5040) meaning I could not check each output individually.

I experimented with Google's python langdetect module and I had a look into ngrams, but it seems that the nature of the cipher causes any variation to appear English.

Would there be any other way to check the output document to check its 'English rating'? What about a combination of I.C. and ngrams?

Thanks in advance!

Try tokenizing the plaintext using an English dictionary. Give higher scores to bigger words to prevent your analyzer from favoring a bunch of one to two letter words. Total the score up and take the highest.

I'm not trying to plug, but there's an (badly written) example in this repo:
https://github.com/wildcardcorp/samson

Here's the code for the analyzer itself:
https://github.com/wildcardcorp/samson/blob/master/samson/analyzers/english_analyzer.py

Example of usage:

>>> from samson.analyzers.english_analyzer import EnglishAnalyzer
>>> message = bytearray(b'stopcollaborateandlisten')
>>> analyzer = EnglishAnalyzer()
>>> analyzer.analyze(message)
105605.2045585186
>>> import random
>>> random.shuffle(message)
>>> message
bytearray(b'nisoabtpenaltdlecoslrato')
>>> analyzer.analyze(message)
22361.397837608132


OFB output jth-block expression clarification Stalling says:

OFB encryption can be expressed as
Cj = Pj⊕E(K, Oj-1)
where
Oj-1 = E(K, Oj-2)
Some thought should convince you that we can rewrite the encryption
expression as:
Cj = Pj⊕E(K, [Cj-1 ⊕Pj-1])

Is he implicitly saying that

[Cj-1 ⊕Pj-1] = Oj-1

? If yes, why?

Is he implicitly saying that
[Cj-1 ⊕Pj-1] = Oj-1

Yes, this is true.

? If yes, why?

Well, we know that:
$$C_{j-1} = P_{j-1} \oplus E(K, O_{j-2})$$
(this is the first formula, replacing $j$ with $j-1$), and we know that:
$$O_{j-1} = E(K, O_{j-2})$$
Combining the two, we get:
$$C_{j-1} = P_{j-1} \oplus O_{j-1}$$
or, in other words:
$$C_{j-1} \oplus P_{j-1} = O_{j-1}$$


Reducing the output of AES MixColumns to one byte per entry I am attempting to manually step through the AES algorithm. I have reached the MixColumns step, and am working with the following values:

30 CA 96 24
32 92 09 23
3F CA 43 63
7D 5A F8 96

My output for the first "row" (multiplying the first row of the constant matrix by each of the four columns in the matrix shown above, which was the output from the ShiftRows step) is as follows:

B4 B2 97 D4

With the following logic:

60 X 96 X 3F X 7D = B4
194 x 1B6 X CA X 5A = B2
12C X 1B X 43 X F8 = 18C (MOD 11B) = 97
48 X 69 X 63 X 96 = D4

For the second cell of the second row, I have the following logic: (01 X CA) X (02 X 92) X (03 X CA) X (01 X 5A), with X used here as a symbol denoting the exclusive or operation. The above simplifies to CA X 124 X 25E X 5A, which evaluates to 3EA. 3EA is clearly too large to be a single output value for MixColumns, which outputs a byte array. Thus, we must reduce it, as 18C above, by taking it MOD 11B. However, 3EA (MOD 11B) evaluates to 2F1, which is still too large.

What is the procedure to be used in further reducing 3EA to a valid output byte for the AES MixColumns function?

For the second cell of the second row, I have the following logic: (01 X CA) + (02 X 92) + (03 X CA) + (01 X 5A), with + used here as a symbol denoting the exclusive or operation. The above simplifies to CA + 124 + 25E + 5A, which evaluates to 3EA.

You have a couple of problems here.  You're doing all your evaluations of these as integers; the problem is that they're not integers, they're elements of $GF(2^8)$.  The field $GF(2^8)$ does have "addition" and "multiplication" operations defined, however they're not the standard integer operations (and in fact, the "addition" operation is the same as exclusive-or').  The standard way of looking at it is that multiplication in $GF(2^8)$ is not integer multiplication followed by an integer modulo operation; one way of implementing it would be a "carryless multiplication" followed a 'binary modulo' operation.  You could do the carryless multiplication first, xor all the results, and then do your binary reduction; however a) 03 X CA isn't 25E (this isn't integer multiplication), instead, it's (CA<<1) + CA = 15E, and b) for the modulo operation, you don't subtract 11B, you exclusive or 11B (or 11B shifted left).

However, instead of getting into all that, for your purposes, the three multiplications within the MixCollumn operation can be simplified to:

$$X \times 1 = X$$

$$X \times 2 = \left\{
\begin{array}{rl}
x<<1 & \text{if } x < 128,\\
(x<<1) \oplus 11B & \text{if } x \ge 128.
\end{array} \right.
$$

$$X \times 3 = (X \times 2) \oplus (X \times 1)$$


How to break CBC cipher with partly known plaintext? I'm learning some IT security and during practice I found an exercise I couldn't solve.

I have an encrypted message with block cipher in CBC mode.
The blocks are one byte long and the first block is an IV. I know 80% of the plaintext which is a form but there are missing parts. I don't know anything about the encryption function.

Which attack method should I use, and where to start?
I know, that $C_1=Enc_k (M_1\oplus C_0)$. I know $C_1$, $M_1$ and $C_0$, the IV.

$\mathrm{Enc}_k$ always transforms the same block value to the same block value. Since blocks are only one byte long, there are only 256 different block values. So you can build a table of those from the parts of the plaintext that you know. Once you've built that table, you can use it in the reverse direction to calculate $\mathrm{Dec}_k$.

$$
\begin{array}{l|l}
x & \mathrm{Enc}_k(x) \\ \hline
0 & \_ \\
1 & \_ \\
\vdots \\
255 & \_ \\
\end{array}
$$

Knowing $M_1$, the equation $C_1 = \mathrm{Enc}_k(M_1 \oplus C_0)$ gives you one entry in the table. More generally, whenever you know the value $M_i$, the equation $C_{i+1} = \mathrm{Enc}_k(M_{i+1} \oplus C_i)$ gives you one entry in the table. Some positions may call $\mathrm{Enc}_k$ on the same input as another position, so it may take more than 256 known bytes in the plaintext, but with a few hundred bytes of known plaintext the probability of missing entries decreases rapidly¹ since the inputs for different values of $i$ are essentially random.

If there are missing values in the table, you can narrow things down in two ways. First, since $\mathrm{Enc}_k$ is a permutation, all the values in the second column are distinct. Second, all the $M_i$ are probably printable characters, which limits the possibilities. Within the scope of the exercise, I'd expect that if there are any blanks, they're easy to fill in with a little hand-driven calculation.

The core of the problem is the 8-bit block. An 8-bit block is far, far too short. In the real world, older block ciphers such as DES and ((X)X)TEA have 64-bit blocks, and modern block ciphers have 128-bit blocks. Even with a 64-bit block, such a table attack is unlikely to give any useful results (the table would require 128 EiB of sttorage, and you'd need roughly that amount of guessable plaintext with a known ciphertext to build it). 64-bit blocks are vulnerable to a sparse version of this attack where you hope that $\mathrm{Enc}_k$ has been called twice on the same input, and this reveals something about the message (if $C_i = C_j$ then $M_i \oplus C_{i-1} = M_j \oplus C_{j-1}$, which reveals the value of $M_i \oplus M_j$, and in particular reveals $M_j$ if you know $M_i$). And you only need about $2^{32}$ blocks of message to have a decent chance of a repeated block value (birthday bound), which makes this attack practical (most famously as Sweet32).

CBC itself with a block cipher with a decent-size block and with a random IV is secure even against chosen-plaintext attacks (IND-CPA). However, it is not at all secure against adaptative chosen-plaintext attacks, where the attacker can submit some plaintext to encrypt after seeing the previous portion of the ciphertext.

   In the adaptative case, I know $C_i$ and am allowed to submit $M_{i+1}$ which lets me learn $C_{i+1} = \mathrm{Enc}_k(M_{i+1} \oplus C_i)$. So I choose $M_{i+1} = C_i \oplus x$ and this way I can learn $\mathrm{Enc}_k(x)$ for an arbitrary $x$. If I've guessed a plausible value for $M_j$ for some $j$, this lets me verify this guess by testing whether $C_{i+1} = C_j$.

CBC as used in practice is not secure in general because it requires padding, since CBC can only encrypt a whole number of blocks. Padding is vulnerable to padding oracle attacks in scenarios where the attacker can submit chosen ciphertext. This is why CBC is deprecated, especially for communication. (It can be ok for storage where the adversary might be able to see ciphertext, e.g. from leaked backups, but has no way to inject ciphertext.)

¹  Unless $\mathrm{Enc}_k$ has some correlation with $M$.


Algorithm complexity: $\mathcal O(n\cdot m)$ vs. $\mathcal O(max(n,m)^2)$ Suppose $A(n,m,k)$ computes

for 1 < i < n do {
  for 1 < j < m do {
    /* some efficient cryptographic operation */
  }
}

where $k$ is a security parameter and integers $n$ and $m$ are upper-bound by a polynomial in that parameter.

  Algorithm $A$ has complexity $\mathcal O(n\cdot m)$, which is quadratic when $n=m$.

Complexity nevertheless seems better than $\mathcal O(max(n,m)^2)$, but we've just seen it isn't.

Can we better compare algorithms with complexity $\mathcal O(n\cdot m)$ and $\mathcal O(max(n,m)^2)$?

The above captures the core aspects of my question. The details are as follows: Algorithm $A$ is part of a voting protocol. Integer $n$ represents the number of candidates and integer $m$ represents the number of cast ballots. So, in practice, $n$ is small and $m$ is large, which gives meaning to $\mathcal O(n\cdot m)$ being seemingly better than $\mathcal O(max(n,m)^2)$, but Big O notation looses that meaning. Is there a way to express it? I suppose we could say "the complexity of algorithm $A$ is linear in the number of cast ballots for small values of $n$", but that seems rather informal. Can we be more precise with regards to "small values of $n$"? Perhaps we just say "the complexity of algorithm $A$ is linear in $n\cdot m$"?

This type of $\mathcal{O}$ usage specific to the problem to indicate some other factor plays a role;

in Bucket sort $\mathcal{O}(n \cdot k)$, $k$ is the number of buckets
in Counting sort $\mathcal{O}(k+n)$, $k$ is the range of the inputs.

In the voting case; the $m$ represents the casted ballots, $n$ represent the candidates, and $m \gg n$.

Using $\mathcal{O}(m^2)$ may hide some important factors especially when comparing different algorithms for the same system.
When the candidates are very small, the algorithm will behave like linear. Using $\mathcal{O}(m^2)$ will hide this.

Prefer to use   $\mathcal{O}(n \cdot m)$.


How can you tell the type of encoding being used? $2y$05$68LWs2pXiEvhVTacJ9PX/elfa1zq9jCBlv61hEw1pCvAHlaJyeMwW

This hash value is 70 characters long. How can I tell what type of encoding was used to generate it? Also, how many bits does each character hold?

That looks like bcrypt.

There are four parts:

$2y - identifier that this is bcrypt in modular crypt format.
$05 - number of key expansion rounds: in this case, it is 25
68LWs...X/e - this is the salt. A total of 128 bits encoded in base64.
lfa1z...MwW - this is the hash. A total of 184 bits encoded in base64.

Since base64 encodes three bytes to four base64 characters, you get 6 bits for each base64 character.


Additive proof of discrete log? Let's say someone has $K$, and I want to prove to them that I know $k$ such $K = k*g$ (where $g$ is some sort of group element). I can use a Schnorr signature.

Is there some protocol for mergable proofs of the above kind. Namely, that given a proof for $k_1$ and $k_2$, you get a proof for $k' = k_1 + k_2$. (Note that you don't necessarily know $k_1$ and $k_2$. You have just seen proofs for them.)

Note that the proof is much weaker, of course. You are not proving that you know $k'$. You are only proving that you have seen proofs of $k_x$ that add to $k'$.

It should also take $\mathcal O (1)$ space in the number of $k_x$ (this would be a corollary if the number of $k_x$ where a secret). Otherwise, the proof would be easy. Simply list the proofs for all the $k_x$. ($\mathcal O(\log x)$ is also acceptable.)

(This is open problem two of the mimble wimble white paper.)

EDIT: Another nice property would that for a proof of $k$, finding a proof for $-k$ should be hard.

Chase et al.: Malleable Proof Systems and Applications. Eurocrypt 2012

This paper is the only one I know of that discuss a problem like this. They consider the problem of combining/modifying NIZK proofs -- for example, if I see a proof that $(A,B,C)=(g^a, g^b, g^c)$ is a DH-tuple ($c = ab$), then I can produce a proof that $(A^2, B^2, C^4)$ is a DH-tuple, even though I don't know their discrete logs.

Their focus is Groth-Sahai-style proofs in groups with bilinear pairings. I don't know how helpful the techniques will be for Schnorr-style proofs.


What is scale-invariance notion of a fully homomorphic encryption scheme? I read this paper https://eprint.iacr.org/2012/078.pdf and I didn't understand what does the author mean with scale-invariance perspective.

The perspective in which we view the ciphertext is accomplished by the algorithms used ? I refer to BitDecomp, PowersOfTwo and the tensor product.

Or the perspective is achieved by decryption with divide q ?

Should I view scale invariance perspective of the ciphertext as I view Fourier transform of a signal ?

While @j.p. is correct that the scale-invariant scheme encodes the plaintext a bit differently than in other FHE schemes, this is mostly just a syntactic point that doesn't really get to the heart of scale invariance.  (Indeed, it is easy to switch between the two encodings of the plaintext, simply by multiplying the ciphertext by an appropriate scalar.  See Appendix A of this paper for details.)

The key property of scale-invariant schemes is that homomorphic multiplication increases the error "rate" (relative to the ciphertext modulus $q$) by a fixed factor, independent of the magnitude of the errors in the ciphertexts.  For example, it doesn't matter whether the ciphertexts have error $\approx 10^2$ for modulus $q=10^6$, or error $\approx 10^5$ for modulus $q=10^9$ (for the same error rate of $10^{-4}$): the error rate in their homomorphic product will be, say, $10^{-2}$.  (I'm using artificially small numbers here for the sake of illustration.)

By contrast, homomorphic multiplication in non-scale-invariant schemes is very sensitive to the magnitude of the errors, because the errors are essentially multiplied.  So in the first case above we would end up with error $\approx 10^4$ for modulus $q=10^6$ (which is fine), but in the second case we would get error $\approx 10^{10}$ for modulus $q=10^9$, which would yield garbage upon decryption.

Non-scale-invariant schemes use modulus reduction to convert the second case into something more like the first, to make the ciphertext safe for multiplication.  Scale-invariant schemes don't need to do this (though it's still useful as an optimization, because decreasing precision leads to faster operations).  More significantly, scale-invariant schemes can be based on a parameterization of LWE that is classically (not just quantumly) as hard as worst-case lattice problems, where we need to use a huge $q \approx 2^n$ and a (still huge, but relatively much smaller) error $\approx q \cdot n^{-d}$, where $d=O(\log n)$ (for example) is the multiplicative depth we want the scheme to be able to handle.


Hashes or ciphers with all rounds executed in parallel? Pretty much every cipher or hash I've seen has multiple rounds the are designed to be run serially one after the other. Has anyone ever designed a fully parallel cipher or hash? This would be one where all rounds are executed in parallel and then the results are combined in some way such as addition or XOR.
It's mostly a theoretical question. It just occurred to me that I've never seen nor heard of such a thing.
It would be interesting from a performance perspective since you could use wide SIMD instructions to compute many rounds at once. It would also be easier to implement in hardware to run in one clock cycle.

Rounds in block ciphers, and in the inner compression or sponge function of a hash, are run sequentially for a security reason: it increases diffusion, which is necessary for security. Examples include the 10, 12 or 14 rounds of AES-128, -192 or -256; and the 64 or 80 rounds of SHA-2. We just do not know how to make a secure cryptographic primitive operating on a moderate-sized block that's secure, deeply parallel, and not very much more costly than what we use today.
Parallelism can and is used at a higher level. One of the virtues of CTR is that parallel implementations compatible with sequential implementations is easy. That applies to AES (in multi threaded implementations or parallel hardware), ChaCha, Gimli (which are amenable to SIMD implementation). Modern hashes often have a provision for parallel implementation using Merkle hash trees (often, just two-levels; e.g. ParallelHash of NIST SP 800-185), but that's at the cost of increasing complexity of non-parallel implementations, which I think is part of why it so far did not catch up in daily practice.


Is differential calculus related to RSA? I'm writing a high school math paper on RSA and I'm wondering if it's possible to relate calculus to RSA. Is calculus used for any part of RSA? It can be for proving equations/theorems, for generating keys, for cracking RSA, etc.

Generally, no. There is no calculus in the design and implementation of the RSA.
There are two things that could add some analysis in the whole scheme of things:

Maybe involving the Prime Number Theorem, which explains why we won't run out of prime numbers to choose from. Some proofs of the theorem use complex analysis (including the simplest known proof, from Donald J. Newman).
About primality testing: In the paper describing the AKS algorithm, "PRIMES is in P", there is a lemma (3.1) which is proven here. Analysis is used in the proof.

You can see that calculus is not directly connected to the RSA cryptosystem but there are some fundamentals that need calculus to be proven.

The quote below is generally true:

  Every part of math is related to any other if you try hard enough. –  Thomas


What is the property of RSA where N=e? In RSA, suppose we know that $e=N$ and we are given the value of $e$.
($N =  p\cdot q$ for some large primes $p$ and $q$; $\gcd(e, \varphi(N) = 1)$

Can we calculate $d$ ($d = e^{-1} \mod \varphi(N)$) without factoring $N$?

No, $e=N$ is no less secure than any other value of $e>1$.

In fact, we can make a stronger statement; if setting $e=N$ allows us to compute the corresponding $d = N^{-1} \mod \phi(N)$, then we can factor $N$ (and hence we can find the $d$ corresponding to any $e$).  This is due to the fact that knowledge of any nontrivial pair $(d,e)$ with $d \cdot e = 1 \mod \phi(N)$ allows us to efficiently find the factorization of $N$.

We don't use $e=N$, not because of security reasons, but because of efficiency. Setting $e=N$ makes the public key operation (encryption, signature verification) far more expensive than it would be if we set $e$ to a small value; given that a large $e$ typically would have no advantage to make up for that, we generally don't use large $e$.

Historical note: when Clifford Cox initially devised his varient of RSA (which wasn't declassified until well after RSA was published), he actually had $e = N$.


AES key expansion for 192-bit In AES-192 key expansion there are 12 rounds and 52 keys.

I am not sure why 52 keys are derived since each block consist of 4 rows and 6 columns (192 bit keys).

So if the block is 4 x 4 then we simply multiply rounds with key size. 13 x 4 = 52 but here we have 4 x 6 matrix (block).

Can someone tell me why we get 52 keys in that case?

For 192 bit key(AES-192), there are 6 columns of 32 bit each i.e 4x6 Matrix. These 192bits of Master Key are shown as k0,k1...k5, i.e 6 words of 32 bit each.

(See page 44 of Book "The Design of Rijndael")

Now k6 will be

k6 = SubByte((RotateWord(k5)) xor K0 Xor Rcon1

k7 = k6 xor k1

k8 = k7 xor k2

and so on...

Since the state in al variants of AES is 128 bit(its the key which is either 128 or 192 or 256 bit) i.e 4 words of 32 bit, the Round Key 0 will consist of k0,k1,k2,k3. The Round Key 1 will consist of k5,k6,k7,k8 and likewise.

We only need 13 x 4 = 52 keys, because the input state is still of 4 words of 32 bit each (128-bit) and each Round Key is also 128 bit. Its only the Master Key which is 192-bits(6 words of 32-bit)

This Animation explains AES-128.


trapdoor commitment from lattice-based assumptions? I'm wondering that is there any equivocal commitment scheme (i.e., trapdoor commitment) can be constructed from lattice-based assumptions? I know there are a lot of commitment schemes from lattices as described in More Efficient Commitments from
Structured Lattice Assumptions (described in the introduction) but I do not identify any trapdoor commitment scheme from lattice-based assumptions. Thus I'm wondering is there any equivocal commitment scheme? Recall that Pedersen commitment is an equivocal commitment but is constructed from Discrete Log assumption.

If you have a (standard) commitment scheme $C$ and zero-knowledge proofs of knowledge (both exist from LWE -- in fact, both exist from one-way functions), then you necessarily have equivocal commitments. Here is a straightforward equivocal commitment $C_e$: committing with $C_e$ is just committing with $C$, and opening a commitment is done by revealing the committed value $m$, together with a proof of knowledge of an opening to $C$ such that the commitment opens to $m$. It is easy to see that the proof of knowledge property implies that $C_e$ is binding, and the zero-knowledge property implies the existence of a simulator which can fake proofs of opening to any $m$, hence the commitment is equivocal.

That being said, I'm pretty sure there are many direct and relatively efficient constructions of equivocal commitments. For example, the LWE-based fully homomorphic trapdoor functions from this paper are in particular equivocal commitments (see page 5 of the paper).


AES+CTR+HMAC Encryption and Authentication on an Arduino In my project we would like to encrypt and authenticate the the communication channel between our server and our Arduino nodes, which relies on an underlying TCP channel.

We have chosen AES in CTR mode as the cryptographic cipher of our choice, transmitting the initialization vector and the message number in clear such that both know which to use (next).

Since encryption is not enough (and integrity actually much better), we are also pondering which authentication algorithm to use. HMAC-SHA256 or simply SHA-256 seem to be suitable candidates. We would encrypt then authenticate.

The questions are:

do we need to authenticate the initialization vector?
is SHA-256 enough for authentication purposes, or should we use HMAC-SHA-256?
if we use HMAC-SHA-256, should we use a different key than the one used for AES encryption?
is SHA256 a good choice to use for the initialization vector? We would use only 128bit of the resulting hash in case of short messages, or multiples of 128 Bit

Or should we pertain to other solutions?

Yes, authenticate the IV. If an attacker changes the IV while keeping the rest of the ciphertext intact, they'll change the message. Just because they can't change the message to an arbitrary value doesn't mean they can't cause harm (if nothing else, they can send random junk until they hit a valid command or a bug in your parser, or feed you invalid data).
SHA-256 doesn't authenticate anything whatsoever. Its use for integrity is that if a message changes, so does its SHA-256 digest, and it's easier to ensure the integrity of 256 bits than of a gigabyte-long message: a giest allows you to do integrity by proxy. But you still need to ensure the integrity of the digest somehow.
HMAC, in contrast, incorporates a secret key, and can only be produced with the knowledge of the secret key, so it provides authenticity. Note that authenticity doesn't imply integrity: an attacker could replay an older, equally valid message.
I'm nowhere nearly a competent enough cryptographer to know whether using the same key for the HMAC and the encryption is a problem, but my gut reaction to “use the same key for” is don't do it. Either keep two separate keys, or if you only have 128 bits of key material, derive two 128-bit keys from these 128 bits.
If you never send the same message twice, then it is valid to use the first (or last) 128 bits of the SHA-256 of the message as an initial nonce (IV) for CTR mode. CTR mode absolutely requires a unique nonce per message; the nonce is commonly generated at random, which ensures unicity even if the messages are identical, but that isn't a requirement unlike some other block chaining modes.
If you send the same message twice with the same IV, the ciphertext will be the same, and eavesdroppers can find out. The only way to remedy this is to have a source of uniqueness. Ideally, you run a cryptographic PRNG on the Arduino, making sure to seed it either with sufficient hardware entropy (I don't know what the Arduino's capabilities are) or with entropy provided securely (with both authentication and confidentiality) from some more capable machine. Another alternative is to send a unique token from the server before the Arduino sends each message, and include that in the message; the token has to be integrity-protected but doesn't need to be confidential.

Now that I've answered your questions, let me answer your question.

Don't do this. Use authenticated encryption (GCM or EAX).

  authenticated encryption is "combined traditional encryption and independent MAC, done properly".