This technique is quite old, actually, and has historically been used to compress RSA keys. It is perfectly safe, provided you don't have access to the original

This technique is quite old, actually, and has historically been used to compress RSA keys. It is perfectly safe, provided you don't have access to the original modulus (the intuition here is that if p is chosen uniformly at random, then next_prime(n/p) will also be (almost) uniformly distributed). Other techniques exist that permit to embed information about d or p inside the modulus (e.g. [7]), but those don't apply in this case. The first appearance of this technique was in [1, §2.1]. Later, Vanstone and Zucherato reinvented and also tried to patent it [2, 3]. Lenstra also joined in [4]. Bernstein and Coppersmith suggested a method, based on lattice reduction, that reduces RSA keys to up to 1/3 of their size [5]. Joye [6] describes a method achieving this without explicitly using lattice reduction. [1] http://link.springer.com/chapter/10.1007%2F3-540-46877-3_42 http://link.springer.com/chapter/10.1007%2F3-540-46877-3_42 [2] http://link.springer.com/article/10.1007/BF00190758 http://link.springer.com/article/10.1007/BF00190758 [3] http://patents.justia.com/patent/6134325 http://patents.justia.com/patent/6134325 [4] http://link.springer.com/chapter/10.1007%2F3-540-49649-1_1 http://link.springer.com/chapter/10.1007%2F3-540-49649-1_1 [5] http://cr.yp.to/sigs/key.html http://cr.yp.to/sigs/key.html [6] http://joye.site88.net/papers/Joy08rsacompr.pdf http://joye.site88.net/papers/Joy08rsacompr.pdf [7] https://eprint.iacr.org/2002/183 https://eprint.iacr.org/2002/183