Has the following method of hiding data been proposed or studied? What is the efficiency or security of this method? What applications could use this method?
Data is to be hidden in a number that is the product of two prime numbers.
One prime number contains the hidden data, and a bigger
prime number indicates the length of the data, constructed using concatenation as follows.
$p = p_0 \ || \ data \ || \ p_{end}\ \ $ and $ \ \ q = q_0 \ || \ marker \ || \ q_{end}$
where $p_0$ and $q_0$ are random $single$ non-zero digits with $p_0 < q_0$,
$data$ is a number with $k$ (decimal) digits,
$marker$ is a random number with $k-1$ non-zero digits followed by $0$, and
$p_{end}$ and $q_{end}$ are random numbers with $n-k-1$ digits.
The encoded data is $N = P \times Q$ where $P$ and $Q$ are the next primes after $p$ and $q$.
$n$ is chosen large enough so that the factorization of a $2n$-digit number is not feasible
and so that, together with choices of $p_{end}$ and $q_{end}$, the construction of $P$ and $Q$ does not cause $data$ or $marker$ to change.
A few comments: (1) Although some constraints on $P$ and $Q$ are known, there is not enough to use "factoring with partial information/known bits". (2) Knowing $P$ and $Q$, in any order, allows the hidden data to be uniquely found. (3) The method is easy to adapt to binary.
Example: $data$ is 271828 with $k$ = 6. For simplicity use $n$ = 12:
$p = \mathtt {1 \underline {271828} 67213}$,
$P = \mathtt {1 \underline {271828} 67221} \ \ $ and
$ \ \ q=\mathtt {6 \underline{97811} \underline {\underline {0}}97478}$,
$Q = \mathtt {6 \underline{97811} \underline {\underline {0}}97499}$
$N = P \times Q = \mathtt {88749616158555602180279}$.
EDIT: Data can be any integer (zero or greater). To emphasise that it need not be prime, I changed the example data from 314159 (which is prime) to 271828 (a composite).
EDIT (March 30): Added "single" to descriptions of $p_0$ and $q_0$ to emphasise that each of $p_0$ and $q_0$ is a single non-zero digit. Note that the size of the data ($k$) is not known in advance, but is indicated by $marker$. Also, the best known result, due to Coppersmith, is that factorization is easy if half the bits of a factor are known.