How can I split a message in parts of similar size or smaller?

Question

I have a 130-160 characters message that I need to split in say, 3 parts, and be able to reconstruct it by recovering all 3 parts. I also need that these parts are type-able, meaning that they can't be too long (I mean not much longer than the original message), and they can't contain weird characters.

I tried with Shamir but the results are too long. I used PassGuardian for that.

Any suggestions?

You can also help me with the tags so the right people is able to find this post.

Answer 1

If the requirement is being able to reconstruct a message of $1280=160\cdot 8$ bits from $3$ parts that are among a set of $2^6$ type-able characters (say $10$ digits, $26$ uppercase letters, $26$ lowercase letters, and $2$ other characters, as in Base64), then no cryptography is required. Simply:

• split the $1280$ bits of the message into $3$ nearly equaly-sized segments, here of $427$, $427$ and $426$ bits;
• append to each segment something allowing to order the $3$ segments and making them a multiple of $6$ bits, e.g. here 00000,00001, 000010; now all messages are $432=72\cdot6$ bits, the two right bits identify the segment number;
• encode each segment as $72$ type-able characters, each encoding $6$ bits.

Decoding, identifying and pasting together the segments is easy and left as an exercise to the reader.

---

If there is the additional requirement that knowledge of $2$ of the $3$ encoded segments should give no useful information about the message, then we need some cryptography. One simple method, optimized to reduce message expansion, is:

• generate a random 128-bit $K$;
• encipher the message with key $K$ (say using AES in CTR mode with implicit null IV);
• split the enciphered message in $427$, $427$ and $426$ bits data segments as above;
• XOR the first $128$ bits of each of the segments, and $K$, forming $K'$;
• splits $K'$ into $3$ segments of $42$, $43$, and $43$ bits, append these to the respective data segments, and append the terminations 00000,0001, 00010, forming $3$ segment of $474=79\cdot6$ bits, that can be identified by their rightmost 2 bits;
• encode each segment as $79$ characters each encoding $6$ bits.

Decoding is easy:

• decode each segment of $79$ characters into $3$ segments of $474$ bits;
• identify each segment by its right two bits;
• remove the terminations, rebuilt $K'$, remove these;
• XOR the first $128$ bits of each of the segments, and $K'$, forming $K$;
• rebuilt the enciphered message;
• decipher it using $K$.

If any of the encoded segments is missing, $K$ can't be formed again.

Notice that we must expand the message with random data somehow, or loose semantic security.