diff --git a/openbsc/src/gprs/gprs_sgsn.c b/openbsc/src/gprs/gprs_sgsn.c
index 84bf512..f92b2de 100644
--- a/openbsc/src/gprs/gprs_sgsn.c
+++ b/openbsc/src/gprs/gprs_sgsn.c
@@ -361,7 +361,7 @@
 	uint32_t ptmsi;
 
 restart:
-	ptmsi = rand();
+	ptmsi = rand() | 0xC0000000;
 	llist_for_each_entry(mm, &sgsn_mm_ctxts, list) {
 		if (mm->p_tmsi == ptmsi)
 			goto restart;