This is even though most of them have already been circumcised as girls - something that usually happens between the ages of four and 10 years old.
Brides undergo genital mutilation 'to be virgins'
Some women in Sudan are opting to undergo female genital mutilation (FGM) a month or two before their wedding to pretend to be virgins.
In the mainly Muslim country this can involve the removal of the clitoris and labia and often includes some stitching to narrow the vaginal opening- a process known as infibulation.
These stitches come away when a woman has sex.
If a bride-to-be opts for further FGM, the operation, usually carried out by midwives, can involve cutting away more of the labia and re-stitching the vagina.
'Couldn't walk for days'
"It was so painful and I had to go and stay with a friend of mine for days until I recovered because I didn't want my mother to know," said Maha, which is not her real name so that her identity can be protected.
"Urinating was an issue and I couldn't walk properly in the first few days."
Maha underwent the operation with two months to go to her wedding to a man "a little bit older" than herself.
"He will never have trust me if he discovers that I have had sex before our marriage," she said.
"He would ban me from going out or even using the phone."
The university graduate in her 20s comes from a state in northern Sudan, which bans FGM.
But the practice is still widely carried out - 87% of Sudanese women aged between 14 and 49 have undergone some form of FGM, according to the UN.
And even though Maha works in the capital, Khartoum - which has not outlawed circumcision - she chose to go home to have the operation secretly at a midwife's house.
She knows the midwife, who agreed to do the operation for a little less than the 5,000 Sudanese pound fee (about $110; £85) that is usually charged.
'I cut as I need the money'
In many cultures where virginity before marriage is important, women opt to have surgery to reconstruct their hymen, a thin layer of tissue that partially covers the opening of the vagina, to hide any sign of past sexual activity.
But "hymenoplasty", as the operation is called, needs to be performed by a surgeon and is not widely available in Sudan - and I'm told only one clinic offers it strictly for married women only.
So stitching to tighten the vaginal opening is the best option. Some midwives also like to cut away more of the labia or other vaginal folds to "tidy things up" during the operation.
Gynaecologist Dr Sawsan Said, a campaigner to eradicate FGM in Sudan, says: "Any changes to the female genitals are considered FGM, whether it's stitching or piercing".
However, none of the procedures can be carried out in hospitals, even in Khartoum, as the Sudanese Medical Council does not allow them.
It would fire any midwife caught doing so and confiscate her equipment.
Yet at three hospitals I visited, midwives were happy to offer me the various procedures.
One even spoke openly about it in front of other nurses and showed me the rooms where it could be performed.
"Do you want me to cut part of the clitoris? If you don't want me to touch it, I won't… but I will make you perfect by cutting a bit of the external labia and stitch them together," she said
Another midwife said she was loath to do them, but sometimes did so as she needed the money.
"I did an infibulation the other day to an 18-year-old girl, who was raped by her cousin. Her mother came here and cried, so I wanted to help them," she said.
"I took an oath to the Saleem Initiative to never cut women or girls again, but I only do it from time to time because I am raising my grandchildren, whose mother passed away, and I need to pay for their school fees."
The Saleema scheme is a UN-backed project launched in 2008 to stop the practice of FGM in Sudan.
But it has a long way to go to change attitudes, especially in a conservative society.
"I wish my future wife would be virgin," a single man in Khartoum told me, saying he would suspect her of cheating on him otherwise.
This is a very common attitude across Sudan, where men expect women to be "stitched".
Yet anti-FGM campaigners are hopeful that things will change given that last month the country repealed a restrictive public order law that controlled how women acted and dressed in public, including banning women from wearing trousers.
It was introduced during the nearly 30-year rule of Omar al-Bashir, who was deposed as president in a coup earlier this year after mass street protests.
Under the public order law, the authorities had sweeping powers to control what women wore, whom they spoke to and saw, and any job they might hold - with any perceived offender facing punishment by flogging, or in rare cases stoning and even execution.
Nahid Toubia, the founder of An Lan initiative - a campaign group to eradicate FGM from Sudan - says young women today are "way more advanced" when compared to their parents' generation.
"They are in conflict - they feel they have the right to have sex but also they have to compromise by re-stitching themselves or even by wearing the hijab."
JOIN OUR PULSE COMMUNITY!
Eyewitness? Submit your stories now via social or: