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

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.

-
If the $160$ characters are arbitrary among $256$ values, and the set of type-able characters has $64$ values, then by a counting argument you need one of the $3$ parts to have $\lceil{160\over 3}\cdot{{\log_2(256)}\over{\log_2(64)}}\rceil=72$ characters, which is hardly type-able. Without arbitrary, you could compress the message beforehand. –  fgrieu Jun 5 '13 at 11:26
@fgrieu I can type up to the length of the original message, so 72 characters is fine. But how do I do that? (does the algorithm have a name?) I'm sorry I'm not a cryptographer, just a developer. –  ChocoDeveloper Jun 5 '13 at 12:05
What are your security goals? From the description it seems like taking the 130-160 character message $m=m_1||m_2||m_3$ (with $m_x$ being between 43 and 53 characters) and splitting it into $m_1$,$m_2$, and $m_3$ would be a valid solution. As it apparently is not: What are your security goals? –  Maeher Jun 5 '13 at 12:19

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.

-
Yes, I needed that additional requirement. Thanks! –  ChocoDeveloper Jun 5 '13 at 22:08
+1 for a working 3-of-3 approach. I'm pretty sure tha 2-of-3 (or X-of-Y) threshold schemes require longer messages; one approach is the very similar ssss and SecretSplitter. –  David Cary Jun 6 '13 at 4:33
@David Cary: Common threshold schemes based on Shamir secret sharing are provably secure without assuming security of a block cipher, but (even in X-Y mode with X=Y) require much longer messages than what I propose. I had to craft a scheme to solve the "results are too long" issue worded in the question. –  fgrieu Jun 6 '13 at 4:48
Yes, your scheme is a pretty clever way to reduce the size. –  David Cary Jun 6 '13 at 5:22